Little Aurilio likes a cute girl in his class. So one day he approaches her and asks her if he can sit with her in class. Now, the cute girl is very fond of mathematics. So she gives a task. The task is as follows -

You are given two integers n and k. compute maximum l for which (fact(n)%pow(k,l))==0 where fact(n) is factorial n and pow(k,l) is k^l. Help Little Aurilio in impressing the cute little girl. 

INPUT
First line contains number of test cases T next T lines contains two integers n and k. 

OUTPUT
output T separate lines each containing Maximum l for which (n!%pow(k,l))==0. 

CONSTRAINTS
T<=10^3
2<=n,k<=10^9


SAMPLE INPUT
3
2 5
3 3
8 2


SAMPLE OUTPUT
0
1
7