Count the zero at the end of N! when represented in base b.

Input

the first line is the number T (1 <= T <= 10^5) 

the Ith line in the T line contains two positive integers N (1 <= N <= 10^18), b (2 <= b <= 10^6)

Output

Consists of T lines, the Ith line is the result of the test i

Example

Input:
6
3 7
5 2
10 3
10 9
1000 2
1000 30

Output:
0
3
4
2
994
249