题目描述

给定质数 $p$，求满足 $p^k|n!$ 的最大整数 $k$。($a|b$ 表示 $b$ 是 $a$ 的倍数)

输入格式

输入一行两个数 $p, n$。

输出格式

输出最大的整数 k。

样例 1 输入

2 3

样例 1 输出

1

数据范围

• 对于 $30\%$ 的数据，$n ≤ 5$。

• 对于 $50\%$ 的数据，$n ≤ 10^6$。

• 对于 $100\%$ 的数据，$p, n ≤ 10^9$。保证 $p$ 是质数。