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~ ! ( ~N~ ! tức là ~N~ giai thừa).

Dữ liệu:

• Dòng đầu tiên của đầu vào 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~.

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

Ràng buộc:

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

Ví dụ:

Sample Input

3
62 7
76 2
3 5

Sample Input

9
73
0