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

Dữ liệu vào

• Dòng đầu tiên của đầu vào chứa số nguyên T cho biết bộ số 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.

Kết quả

• Ứ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à ước của N!.

Ràng buộc

~ 1 \leq T \leq 100; 1 \leq N \leq 10^9; 2 \leq p \leq 10^5~

Ví dụ:

INPUT

   3
   62 7
   76 2
   3 5

OUTPUT

   9
   73
   0