Given a positive integer $M$, Bob needs to find the minimum positive integer $N$ so that $N!\equiv 0(\mathrm{mod}M)$.

Since $M$ is huge, Bob will give you $K$ integers, denoted as $e_1,e_2,\dots ,e_K$, such that $M=\prod _{i=1}^K{p}_i^{e_i}$, where $p_i$ is the $i$-th smallest prime number. It is guaranteed that $p_i\cdot e_i\le {10}^{18}$

Input Specification

The first line of input contains an integer $T$ $(1\le T\le {10}^4)$, the number of test cases.

Each of the following $T$ blocks contains two lines of input. The first line contains an integer $K$ $(1\le K\le 100)$, the number of prime factors. The second line contains $K$ integers $e_i$ $(0\le p_i\cdot e_i\le {10}^{18})$, indicating the $i$-th prime's exponent.

Output Specification

Output one integer for each test case, the smallest positive integer $N$ so that $N!\equiv 0(\mathrm{mod}M)$.

Constraints

Subtask	Points	Additional constraints
$1$	$10$	$T=1$, $p_i\cdot e_i\le {10}^5$.
$2$	$25$	$T\le 1000$, $p_i\cdot e_i\le 1000$.
$3$	$30$	$T\le {10}^3$, $p_i\cdot e_i\le {10}^{18}$.
$4$	$35$	No additional constraints.

Sample Input

1
5
1 1 1 1 1

Sample Output

11

Explanation

$M=2^1\times 3^1\times 5^1\times 7^1\times {11}^1=2310$, and the minimum $N$ is $11$.