Aki 喜欢数字,尤其是那些尾随零的数字。例如,数字 $$$9200$$$ 有两个尾随零。 Aki 认为数字后面的零数字越多,它就越漂亮。
然而,Aki 认为,数字的尾随零的数量不是静态的,而是取决于它所表示的基数(基数)。因此,他考虑了一些带有一些数字和基数的场景。现在,由于他使用的数字变得相当奇怪,他要求你帮助他计算这些数字的美丽程度。
给定两个整数 $$$n$$$ 和 $$$b$$$(以十进制表示),您的任务是计算 $$$n\,!$$$($$$n$$$ 的阶乘)的 $$$b$$$ 元(以 $$$b$$$ 的基数/基数)表示形式中尾随零数字的数量。
输入
输入的唯一行包含两个整数 $$$n$$$ 和 $$$b$$$ ($$$1 \le n \le 10^{18}$$$, $$$2 \le b \le 10^{12}$$$)。
输出
打印唯一的整数 - $$$n!$$$ 的 $$$b$$$ 元表示中尾随零数字的数量
示例
输入 #1
6 9
输出 #1
1
输入 #2
38 11
输出 #2
3
输入 #3
5 2
输出 #3
3
输入#4
5 10
输出#4
1
注意
在第一个示例中,$$$6!_{(10)} = 720_{(10)} = 880_{(9)}$$$。
在第三个和第四个示例中,$$$5!_{(10)} = 120_{(10)} = 1111000_{(2)}$$$。
如果 $$$x = d_1 b^{k - 1} + d_2 b^{k - 2} + \ldots + d_k b^0$$$,则 $$$x$$$ 在 $$$b$$$ 进制中的表示为 $$$d_1, d_2, \ldots, d_k$$$,其中$$$d_i$$$ 是整数,$$$0 \le d_i \le b - 1$$$。例如,第一个示例中的数字 $$$720$$$ 表示为 $$$880_{(9)}$$$,因为 $$$720 = 8 \cdot 9^2 + 8 \cdot 9 + 0 \cdot 1$$$。
您可以在此处阅读有关碱基的更多信息。