Số 0 tận cùng của giai thừa

Cho hai số nguyên $n$ và $b$. Hãy đếm số chữ số $0$ ở tận cùng (bên phải) của $n!$ khi $n!$ được biểu diễn trong hệ cơ số $b$.

Ở đây $n!=1·2·3\cdots n$ là giai thừa của $n$. Số chữ số $0$ tận cùng của một số $x$ trong hệ cơ số $b$ là số mũ lớn nhất $k$ sao cho $b^k$ là ước của $x$.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $n$ và $b$.

Dữ liệu ra

In ra một số nguyên duy nhất, là số chữ số $0$ tận cùng của $n!$ trong hệ cơ số $b$.

Ràng buộc

• $1\le n\le {10}^{18}$
• $2\le b\le {10}^{12}$

Ví dụ