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 giai thừa.

Đầu vào

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

Đầu ra:

• Ứng với mỗi bộ dữ liệu đầu vào, 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 giai thừa.

Ràng buộc

• ~ 1 \leq T \leq 100 ~

• ~ 1 \leq N \leq 10^5 ~

• ~ 2 \leq p \leq 10^5 ~

Ví dụ

Đầu vào

    3

    62 7

    76 2

    3 5

Đầu ra

    9

    73

    0