CF1114C.Trailing Loves (or L'oeufs?)

The number "zero" is called "love" (or "l'oeuf" to be precise, literally means "egg" in French), for example when denoting the zero score in a game of tennis.

Aki is fond of numbers, especially those with trailing zeros. For example, the number $9200$ has two trailing zeros. Aki thinks the more trailing zero digits a number has, the prettier it is.

However, Aki believes, that the number of trailing zeros of a number is not static, but depends on the base (radix) it is represented in. Thus, he considers a few scenarios with some numbers and bases. And now, since the numbers he used become quite bizarre, he asks you to help him to calculate the beauty of these numbers.

Given two integers $n$ and $b$ (in decimal notation), your task is to calculate the number of trailing zero digits in the $b$-ary (in the base/radix of $b$) representation of $n\,!$ (factorial of $n$).

数字“零”被称为“爱”（更准确地说是法语中的“l'oeuf”，字面意思是“蛋”），例如在网球比赛中表示零分时。

Aki 非常喜欢数字，尤其是那些末尾带有零的数字。例如，数字 $9200$ 有两个末尾零。Aki 认为，一个数字末尾零的个数越多，它就越漂亮。

然而，Aki 相信，一个数字末尾零的个数并非固定不变，而是取决于该数字所采用的进制（基数）。因此，他考虑了若干涉及特定数字与进制的情形。现在，由于他所用的数字变得相当奇特，他请你帮他计算这些数字的“美丽值”。

给定两个十进制整数 $n$ 和 $b$，你的任务是计算 $n\,!$（即 $n$ 的阶乘）在 $b$ 进制（以 $b$ 为基数）表示下的末尾零的个数。

The only line of the input contains two integers $n$ and $b$ ($1 \le n \le 10^{18}$, $2 \le b \le 10^{12}$).

输入仅包含一行，其中有两个整数 $n$ 和 $b$（$1 \le n \le 10^{18}$，$2 \le b \le 10^{12}$）。

Print an only integer — the number of trailing zero digits in the $b$-ary representation of $n!$

输出一个整数——即 $n!$ 的 $b$-进制表示中末尾零的个数。

In the first example, $6!_{(10)} = 720_{(10)} = 880_{(9)}$.

In the third and fourth example, $5!_{(10)} = 120_{(10)} = 1111000_{(2)}$.

The representation of the number $x$ in the $b$-ary base is $d_1, d_2, \ldots, d_k$ if $x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$, where $d_i$ are integers and $0 \le d_i \le b - 1$. For example, the number $720$ from the first example is represented as $880_{(9)}$ since $720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$.

You can read more about bases here.

在第一个例子中，$6!_{(10)} = 720_{(10)} = 880_{(9)}$。

在第三个和第四个例子中，$5!_{(10)} = 120_{(10)} = 1111000_{(2)}$。

若数 $x$ 在 $b$ 进制下的表示为 $d_1, d_2, \ldots, d_k$，则满足 $x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$，其中 $d_i$ 为整数，且 $0 \le d_i \le b - 1$。例如，第一个例子中的数 $720$ 表示为 $880_{(9)}$，因为 $720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$。

关于进制的更多信息，请参阅此处。