Cho số nguyên dương $N, M$.

Hãy tìm số $K$ lớn nhất sao cho $N!$ chia hết cho $M^K$ nhưng không chia hết cho $M^{K+1}$.

Input

• Gồm một dòng, ghi số $N, M (N <= 2*10^9; M <= 30000)$

Output

• Gồm một dòng, ghi số $K$ cần tìm

Sample Input

7 3

Sample Output

2