Steve bị ốm phải nghỉ học và nhờ các bạn gửi bài tập Tin về qua Mail. Đọc lướt qua đề Steve thấy đề dễ đến mức độ đáng ngờ: yêu cầu xác định xem ~n!~ kết thúc bởi bao nhiêu số ~0~. Đang định gọi điện hỏi lại cho chắc chắn thì Steve nhận được mail thứ hai nhắc nhở là nhớ phải tính ~n!~ theo cơ số ~k~ vì nội dung bài học hôm nay là biến đổi cơ số. Quả thật bài tập không phải thuộc diện dễ nhằn!

Yêu cầu

Cho các số nguyên dương ~n~ và ~k~ ở hệ ~10~. Hãy xác định ~n!~ trong cơ số ~k~ kết thúc bởi bao nhiêu số ~0~.

Dữ liệu

Gồm một dòng chứa 2 số nguyên ~n~ và ~k~ ~(1 \le n \le 10^{18}, 2 \le k \le 10^9)~.

Kết quả

Đưa ra một số nguyên – số lượng số ~0~ tìm được.

Input

20 7

Output

2