Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CPPPRI08 - PRIME 8

Cho số tự nhiên N và số nguyên tố P. Nhiệm vụ của bạn là tìm số x lớn nhất để N! chia hết cho px .

Ví dụ với N=7, p=3 thì x=2 là số lớn nhất để 7! Chia hết cho 32 .

Input

Dòng đầu tiên đưa vào số lượng bộ test T.

Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là cặp số N, p được viết cách nhau một vài khoảng trống.

T, N, p thỏa mãn rang buộc : 1≤T≤100; 1≤N≤105 ; 2≤p≤5000

Output

Đưa ra kết quả mỗi test theo từng dòng.

Example

Input Output
3
62 7
76 2
3 5
9
73
0


Được gửi lên bởi:adm
Ngày:2019-10-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP CPP14

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.