Bậc của thừa số nguyên tố trong N!.

Bối cảnh

Bài toán được mô tả qua yêu cầu và dữ liệu dưới đây.

Yêu cầu

Cho số tự nhiên N và số nguyên tố P. Nhiệm vụ của bạn là tìm số x lớn nhất để N! chia hết cho p^x. Ví dụ với N=7, p=3 thì x=2 là số lớn nhất để 7! Chia hết cho 3^2.

Input

Cặp số N, p được viết cách nhau một khoảng trống.(1≤N≤10^14; 2≤p≤5000).

Output

Đưa ra kết quả trên một dòng.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

7 3

Output

2

Thông tin học tập

• Buổi: B08
• Concepts: advanced arithmetic and number theory
• Giới hạn kiến thức: B01-B08
• Time limit: 2 seconds
• Memory limit: 20 MB
• Point: 10