题目描述

你醒了。

地上散落着写满文字的纸张，不远处的门紧紧锁着。

你试图寻找窗户，但是这里除了门，没有任何出口。

地上一张纸熠熠发光。你拾起它，上面写着一个大大的感叹号。

你忽然明白了什么。

众所周知，对于一个正整数$N$，它的阶乘$N!=\prod_{i=1}^Ni$。特别的，$0!=1$。

小$C$在计算一个正整数$N$的阶乘，但是他只想知道在$a$进制下，运算结果的末尾有多少个$0$。

输入输出格式

输入格式

一行两个正整数$N,a$

输出格式

输出在$a$进制下，$N!$末尾的$0$的数量。

样例

输入

200 10

输出

59

数据范围

对于$20\%$的数据，有$0\le N\le20$，$0<a\le20$。

对于$20\%$的数据，有特殊性质：对于任何一个$a$的素因数$p$，有$p^2\nmid a$。

对于$50\%$的数据，有$0\le N\le 10^6$，$0<a\le10^6$。

对于$100\%$的数据，有$0\le N\le 10^{18}$，$0\lt a\le 10^{12}$。