测试数据来自 WAOI/1000

题目描述

你醒了。

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

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

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

你忽然明白了什么。

众所周知，对于一个正整数\(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}\)。