Given a positive integer ~M~, Bob needs to find the minimum positive integer ~N~ so that ~N! \equiv 0 \pmod{M}~.

Since ~M~ is huge, Bob will give you ~K~ integers, denoted as ~e_1, e_2, \ldots, 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 \pmod{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~.