Trong tiết học môn Toán, lớp của bạn Vương được học về cách tính giai thừa của một số tự nhiên ~N~, kí hiệu ~N!~ ~(N \ge 2)~ như sau:

~N! = N \times (N - 1) \times (N - 2) \times ... \times 1~

Ví dụ: ~3! = 3 \times 2 \times 1~.

Cô giáo đưa ra một bài tập liên quan đến giai thừa. Em hãy viết chương trình giúp Vương và các bạn giải quyết bài toán.

Yêu cầu

Cho số tự nhiên ~N~ và số nguyên tố ~K~. Hãy đưa ra số mũ ~m~ lớn nhất sao cho ~K^m~ là ước của ~N!~.

Dữ liệu đầu vào

• Dòng đầu tiên chứa số nguyên dương ~T~ ~(1 \le T \le 10^2)~ là số bộ dữ liệu cần kiểm tra.
• ~T~ dòng tiếp theo mỗi dòng chứa một cặp số ~N~ và ~K~ ~(2 \le N \le 10^5;\ 2 \le K \le 10^5)~, các số cách nhau bởi một dấu cách trống.

Dữ liệu đầu ra

Gồm ~T~ dòng, mỗi dòng chứa một số nguyên dương ~m~ thỏa mãn yêu cầu bài toán.

Ràng buộc dữ liệu

• 70% số test với ~1 \le T \le 10;\ 2 \le N \le 10^2~ và ~2 \le K \le 10^2~;
• 30% số test với ~10 < T \le 10^2;\ 10^2 < N \le 10^5~ và ~10^2 < K \le 10^5~.

Ví dụ

Ví dụ 1

INPUT

3
2 3
15 5
64 7

OUTPUT

0
3
10