Cho số tự nhiên ~N~ và số nguyên tố ~p~. Hãy tìm số nguyên không âm ~x~ lớn nhất sao cho ~N!~ chia hết cho ~p^x~.

Nói cách khác, cần tìm số lần xuất hiện của thừa số nguyên tố ~p~ trong phân tích thừa số nguyên tố của ~N!~.

Input

Gồm một dòng chứa hai số nguyên ~N~ và ~p~.

Constraints

• ~1 \le N \le 10^{14}~
• ~2 \le p \le 5000~
• ~p~ là số nguyên tố.

Output

In ra một số nguyên duy nhất là giá trị lớn nhất của ~x~ sao cho ~N!~ chia hết cho ~p^x~.

Sample Input 1

7 3

Sample Output 1

2

Explanation

Ta có:

~7! = 5040~

Trong phân tích thừa số nguyên tố của ~5040~, số ~3~ xuất hiện ~2~ lần.

Vì vậy ~7!~ chia hết cho ~3^2~, nhưng không chia hết cho ~3^3~.

Kết quả là ~2~.