Given \(N\) and a prime \(p\), find the largest \(x\) such that \(p^x\) divides \(N!\).

Input

One line containing \(N\) and \(p\).

The input satisfies:

• \(1 \le N \le 10^14\)
• \(2 \le p \le 5000\)
• p is prime.

Output

Print \(x\).

Example

Input

7 3

Output

2