Description

求出 $n$ 的阶乘在 $k$ 进制表示下末尾 $0$ 的个数。

$n$ 的阶乘 $n!$ 为 $1\times 2\times 3\times \cdots \times n$。特别地，$0$ 的阶乘为 $1$。

Input Format

一行两个整数 $n$ 和 $k$。

Output Format

输出一个整数，表示 $n!$ 在 $k$ 进制表示下末尾 $0$ 的个数。

Sample

输入样例：

10 40

输出样例：

2

Hint

对于 $20\%$ 的数据，$n\le 10^6，k=10$

对于另外 $20\%$ 的数据，$n\le 20，k\le 36$

对于 $100\%$ 的数据，$n\le 10^12，k\le 10^12$。