Trailing Zeros in Factorial in Arbitrary Base

SOL君 loves factorial and SOL菌 loves number bases. One day, SOL君 casually computed n!. SOL菌, not willing to concede defeat, challenged him by asking: What is the number of trailing zeros in the representation of n! when written in base k?

Note: Instead of computing the huge n!, you are required to determine the number of trailing zeros in its base-k representation using number theoretic methods.

Hint: If k has the prime factorization \(k= p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}\), then the number of trailing zeros is given by:

\[ \min_{1 \le i \le m} \left\lfloor \frac{\nu_{p_i}(n!)}{a_i} \right\rfloor, \] where \(\nu_{p}(n!)\) is the exponent of the prime \(p\) in n!, computed by \(\nu_p(n!)=\sum_{j\ge1}\left\lfloor \frac{n}{p^j}\right\rfloor\).

inputFormat

The input consists of a single line containing two integers n and k separated by spaces.

\(1 \leq n \leq 10^{9}\), \(2 \leq k \leq 10^{9}\).

outputFormat

Output a single integer representing the number of trailing zeros in the base-k representation of n!.

sample

5 10

1