All the veteran contestants know that the number of occurrences of prime number p in factorial n (n!) can be found using the formula below: ⌊⌋⌊⌋⌊⌋⌊⌋ f(n,p)= n + n + n + n +··· p p2 p3 p4 This formula can effectively be used to find the number of trailing zeroes of n!, in any number system. Let z(n, b) be a function which denotes the number of trailing zeroes of n!, in number system b. A new function soz(n) is defined as ∑n i=1 straight forward way. Given the value of n and the base b, your job is to find out the value of soz(n, b). Input The input file contains at most 1200 lines of inputs. Each line contains two integers n (0 ≤ n ≤ 4000000000) and b (1 < b ≤ 100000). Here the base b is a square free number. A square free number is a number which is not divisible by any square number other than 1. So the value of b can be 10 but the value of b cannot be 24, as 24 is divisible by a square 4. Input is terminated by a line where the value of n and b is zero. This line should not be processed. Output For each line of input except the last one produce one line of output. This line contains an integer which denotes the value of soz(n,b). You can assume that the output integers will fit in 64-bit signed integers. Sample Input 10 10 10 14 10000000 10 00 Sample Output 7 4 12499951484374 soz(n, b) = While the computation of z(n,b) is quite easy, the computation of soz(n) is not that efficient in a z(i, b)