ShyWoou là một thanh niên rất thích những bài toán liên quan đến con số. Thấy thế, trong mùa Translate COVID vô cùng chán nản này, thầy Hùng quyết định đánh đố học trò của mình:

Thầy sẽ cho bạn 2 số nguyên dương \(n\) và \(m\) bất kỳ, nhiệm vụ của bạn là tìm số nguyên dương \(k\) lớn nhất sao cho \(n!\) \(=\) \(1 \times 2 \times 3 \times 4 \times .. \times n\) chia hết cho \(m^k\).

Nếu không tìm được số \(k\) thõa mãn, in ra \(-1\).

Cảm thấy độ quá dễ của bài toán, ShyWoou đành nhường câu đố này cho các bạn!

Input

• Dòng đâu tiên chứa số \(2\) nguyên dương \(n, m\) \((2 ≤ n, m ≤ 10 ^ {12})\)

Output

• In ra số nguyên dương \(k\) lớn nhất thõa mãn đề bài.

Sample Input

6 6

Sample Output

2

Giải thích

\( n = 6! = 720\), \( m = 6 \), số \(k\) lớn nhất là \(2\) nên \(m = 6 ^ 2 = 36\) và \(720\) \(\vdots\) \(36\).

Giới hạn

• \(40\)% số tests đầu tiên có \(n ≤ 10^6\).

• \(60\)% số tests còn lại không ràng buộc gì thêm.