For n positive integer, let F(n) = 1! × 2! × 3! × 4! × ... × n!, product of factorial(i) for i in [1..n],

For p a prime number, and n an integer, and let V(p, n) = max({i>=0 integer, such that p^i divides F(n)}).

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given two integers p a prime number, and n.

Output

For each test case, you have to print V(p, n).

Example

Input:
2
2 3
3 4

Output:
2
2

Constraints

0 < T < 10^5
1 < p < 10^18, a prime number
0 < n < 10^18

p and n are log-uniform independent randomly distributed.

Four lines of Python code can get AC in half the time limit. (Edit 2017-02-11, after compiler changes)
;-) Have fun.