Cho số nguyên N, và một số nguyên tố p. Tìm lũy thừa lớn nhất của p mà là ước của N!

Đầu vào: Dòng đầu tiên chứa số nguyên T cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên N và p

Đầu ra: Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng số mũ lớn nhất của lũy thừa cơ số p mà là ước của N!

Ràng buộc: 1 ≤ T ≤ 100; 0 ≤ N ≤ 10⁵; 2 ≤ p ≤ 10⁵;