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 ≥ 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 vào:

Từ tệp văn bản SOMU.INP gồm:

• Dòng đầu tiên chứa số nguyên dương \(T\) \((1 ≤T≤ 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 ≤N≤ 10^5; 2 ≤K≤ 10^5)\), các số cách nhau bởi một dấu cách trống.

Kết quả:

Ghi ra tệp văn bản SOMU.OUT 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.

Ví dụ:

Giới hạn:

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