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