BichSonNhat 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, BichSonNhat đà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 ^ 6)\)

Output

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

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n ≤ 10\).

• Subtask \(2\) (\(30\%\) số điểm): \(n ≤ 10^3\).

• Subtask \(3\) (\(40\%\) số điểm): không ràng buộc gì thêm.

Example

6 6

2