SP18667 FACTMULP - Product of factorials (hard)

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)})_**.

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_**.

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.