题目描述

给定正整数 $n, k$，已知非负整数 $x$ 满足 $n! \bmod k^x = 0$，求 $x_{max}$ 。

输入格式

本题包含多组数据，请处理至文件末尾。

对于每组数据，共有一行，两个整数，表示 $n, k$。

输出格式

对于每组数据，输出一行，一个整数，表示 $x_{max}$。

样例

input

10 2
5000000000000000000 2
5000000000000000000 10000000000000

output

8
4999999999999999981
96153846153846153

数据范围与提示

对于 $40\%$ 的数据，$k \leqslant 2\times 10^7$，$n \leqslant 2\times 10^9$，数据组数 $ \leqslant 50$。
对于 $100\%$ 的数据，$1<k \leqslant 10^{13}$，$1 \leqslant n \leqslant 5\times 10^{18}$，数据组数 $\leqslant 200$。