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

Output

For each test case, you have to print V(p, p^e).
As the answer may not fit in a 64-bit container, just output your answer modulo 10^9+7.

Example

Input:
1
2 2

Output:
5

Constraints

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

p and e are log-uniform independent randomly distributed. Warning : input contains tricky cases too.

A single line of human-readable-Python code can get AC in the third of the time limit. A fast C code ends in 0.04s. (edit 2017-02-11, after compiler changes)
;-) Have fun.