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