FACTBASE - Count Zero

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

Added by:Lê Tiến Khoa
Date:2013-01-15
Time limit:0.200s-1.399s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2013-01-27 19:43:36 Francky
The answer for the last case 1000 30 should be 34, isn't it ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.