Số mũ

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:

Ví dụ: \(3! = 3 \cdot 2 \cdot 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!\).

Input

• 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.

Output

Ghi ra \(T\) dòng, mỗi dòng chứa một số nguyên \(m\) thỏa mãn yêu cầu bài toán.

Scoring

• (\(70\%\)) \(1 \le T \le 10\), \(2 \le N \le 10^2\), \(2 \le K \le 10^2\);

• (\(30\%\)) \(10 < T \le 10^2\), \(10^2 < N \le 10^5\), \(10^2 < K \le 10^5\).