John is very good in shooting. We wants to get admitted in HackerEarth Shooting Academy (HESA). But HESA take very hard interview process to select the candidates. In the Interview process, an assignment is given to John.

In this assignment, some amount X will be given to John. There are some targets to shoot and to fire a bullet there is some cost P is associated. When John will fire a bullet, P amount will be divided from its amount X.

NOTE: The amount will be divided if and only if P completely divides X.

At last, John will have to tell, On now many targets he shoot i.e. N and as well as remaining amount of the John. Help John to get selected in HESA.

INPUT:

First line contains number of test cases T.

For each test case, a single line represents two space separated integers X and P.

OUTPUT:

For each test case, print the value of N.

Constraints:

1 <= T <= 10

1 <= X , P <= 100000