Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3621
Factorial Problem in Base K

Time Limit: 2 Seconds      Memory Limit: 65536 KB

How many zeros are there in the end of s! if both s and s! are written in base k which is not necessarily to be 10? For general base, the digit order is 0-9,A-Z,a-z(increasingly), for example F4 in base 46 is actually 694 in base 10,and f4 in base 46 is 1890 in base 10.


There are multiple cases(less than 10000). Each case is a line containing two integers s and k(0 ≤ s < 2^63, 2 ≤ k ≤ 62).


For each case, output a single line containing exactly one integer in base 10 indicating the number of zeros in the end of s!.

Sample Input

101 2
12 7

Sample Output


Author: ZHANG, Debing
Contest: ZOJ Monthly, June 2012
Submit    Status