When n! is written in base b, it may end in a run of zero digits. Given n and b, report how many trailing zeros n! has in base b. Equivalently, this is the largest integer k such that b**k divides n! (and 0 if no positive power of b divides n!).
Input format
A single line with two integers n and b.
Output format
A single integer: the number of trailing zeros of n! written in base b.
Constraints
- 0 <= n <= 1000000
- 2 <= b <= 1000