For a given prime , define as the multiplicity of in , i.e. the number of times appears in the prime factorization of .

For a given (prime) and , let be the number of integers such that and is divisible by . Here denotes the factorial of .

Your job is to calculate given and .

Input Format
The first line contains the number of test cases .
Each of the next lines contains two integers and separated by a space.

Output Format
For each test case, output one line containing .

Constraints



is prime

Sample input

2
2 6
3 6

Sample Output

2
2

Explanation
Here are the first 6 factorials: 1, 2, 6, 24, 120, 720.

The multiplicities of 2 in these numbers are: 0, 1, 1, 3, 3, 4.
Exactly two of these are divisible by 2 (0 and 4), so .

The multiplicities of 3 in these numbers are: 0, 0, 1, 1, 1, 2.
Exactly two of these are divisible by 3 (0 and 0), so .