Bài 1 (6,0 điểm)   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 ≥ 2) như sau: N! = N*(N - 1)*(N - 2)*…*1. Ví dụ: 3! = 3*2*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²) 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⁵; 2 ≤ K ≤ 10⁵), 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.