SP18662 FACTMULO - Product of factorials (again)

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

For each test case, you have to print **_V(p, n)_**.