Kí hiệu ~N!~ (đọc là ~N~ – giai thừa) là tích các số tự nhiên bắt đầu từ ~1~ đến ~N~. Cho hai số nguyên dương ~N~ và ~P~ trong đó ~P~ là số nguyên tố không vượt quá ~N~.

Yêu cầu: Tìm số nguyên dương ~K~ lớn nhất sao cho ~P^K~ là ước của ~N!~

Input

• Dòng thứ nhất chứa số ~N~
• Dòng thứ hai chứa số ~P~

Output

• Số ~K~ lớn nhất theo yêu cầu

Giới hạn

• 100% số test có ~n \le 10^9~

Ví dụ

Sample input

19 3

Sample output

8