题目描述

编程计算$n!$ 在 $k$ 进制表示下末尾 $0$ 的个数。

输入格式

每组输入仅包含一行：两个整数 $n,k$。

输出格式

输出一个整数：$n!$ 在 $k$ 进制下后缀 $0$ 的个数。

输入输出样例 #1

输入 #1

10 40

输出 #1

2

说明/提示

• 对于 $20\%$ 的数据，$n \le 1000000, k = 10$
• 对于另外 $20\%$ 的数据，$n \le 20， k \le 36$
• 对于 $100\%$ 的数据，$n \le 10^{12}，k \le 10^{12}$

对于所有数据保证$k !=1$；