题目描述

一个正整数 $x$ 的 $b$ 进制表示，指把 $x$ 写成以 $b$ 为基数的形式，其中每位数字取自 $0,1,\ldots,b-1$。例如 $120$ 的二进制表示是 $1111000_2$。

给定两个正整数 $n$ 和 $b$，求 $n!$（$n$ 的阶乘）的 $b$ 进制表示中，末尾连续的 $0$ 的个数。

输入格式

一行两个正整数 $n, b$，其中 $n$ 是阶乘的参数，$b$ 是进制，用空格隔开。

输出格式

一行一个整数，表示 $n!$ 的 $b$ 进制表示中末尾连续的 $0$ 的个数。

样例 #1

5 2

3

样例解释 #1

$5! = 120$，写成二进制是 $1111000_2$，末尾有 $3$ 个连续的 $0$，所以答案是 $3$。

样例 #2

6 4

2

样例解释 #2

$6! = 720$，写成四进制是 $23100_4$，末尾有 $2$ 个连续的 $0$，所以答案是 $2$。

样例 #3

100 2

97

样例解释 #3

$100!$ 的数值非常大，无法直接列出。其二进制表示末尾连续的 $0$ 的个数为 $97$。

数据范围

对于所有数据，$1 \le n \le 10^6$，$2 \le b \le 10^6$。

本题采用捆绑测试。 只有通过一个子任务的全部测试点，才能获得该子任务的分数。