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

Input

The first line is the number T (1 ≤ T ≤ 10⁵) 

The Ith line in the T line contains two positive integers N (1 ≤ N ≤ 10¹⁸), b (2 ≤ b ≤ 10⁶)

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