Description

SOL 君 likes factorials, while SOL 菌 enjoys studying number bases.

One day, SOL 君 showed off to SOL 菌 by casually computing the factorial of $n$.

SOL 菌 was unconvinced and immediately wanted to compute the number of trailing zeros of this number in base $k$.

However, SOL 菌 is not skilled enough, so he asks you for help.

Input Format

Each input contains a single line with two integers $n,k$.

Output Format

Output a single integer: the number of trailing zeros of $n!$ in base $k$.

10 40

2

Hint

• For $20\%$ of the testdata, $n \le 1000000, k = 10$.
• For another $20\%$ of the testdata, $n \le 20， k \le 36$.
• For $100\%$ of the testdata, $n \le 10^{12}，k \le 10^{12}$.

Update

1. Each test point contains only one test case.
2. $k$ will not be $1$.
3. Now the std does not overflow long long.
4. If there is any problem with the testdata, contact icy (it is recommended not to code to the data).

Translated by ChatGPT 5