题目背景

小 A 和小 B 是好朋友。

题目描述

小 A 很喜欢阶乘。而小 B 很喜欢研究进制。

这一天，小 A 跟小 B 炫技，随口算出了n的阶乘。

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

但是小 B 太菜了于是请你帮忙。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

10 40

输出 #1

2

说明/提示

对于20%的数据，n <= 1000000， k = 10

对于另外20%的数据，n <= 20， k <= 36

对于100%的数据，n <= 10^12，k <= 10^12