题目背景

SOL 君（炉石主播）和 SOL 菌（完美信息教室讲师）是好朋友。

题目描述

SOL 君很喜欢阶乘。而 SOL 菌很喜欢研究进制。

这一天，SOL 君跟 SOL 菌炫技，随口算出了 $n$ 的阶乘。

SOL 菌表示不服，立刻就要算这个数在 $k$ 进制表示下末尾 $0$ 的个数。

但是 SOL 菌太菜了于是请你帮忙。

输入格式

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

输出格式

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

10 40

2

提示

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

update

1. 每个测试点只包含一组数据；

2. k 不会为 $1$；

3. 现在 std 没有爆 long long；

4. 对数据有问题联系 icy（建议大家不要面向数据编程）。