beecrowd | 1697

Jaida and Multiply Game

By Bugs, Lucas y Coyote, Universidad Católica San Pablo PE Peru

Timelimit: 2

Jaida likes positive integers very much, currently she is playing a game called "multiply game".

"Multiply game" is just an educational game in which you have a list of N numbers. You can take two of them and add the their product to the list. You can do this as many times as you want.

Jaida wants the list to contain all the numbers from 1 to X (with possible repetitions or greater numbers). Help little Jaida telling her what is the maximum value of X she can achieve.


The first line in the input contains a number T which is the number of test cases. Every test case is described by 2 lines:

The first line contains number N (0 < N <= 106) as described in the statement. The second line contains N positive integers ai, which are the initial numbers in Jaida's list (0 < ai <= 109).


For each test case print a line containing the maximum value X Jaida can achieve. If it is not possible, output 0.

Sample Input Sample Output


1 2 3 4 5 12
2 3 4
1 2 3