bee 1697 - Jaida and Multiply Game

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.

Input

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 <= 10⁶) as described in the statement. The second line contains N positive integers a_i, which are the initial numbers in Jaida's list (0 < a_i <= 10⁹).

Output

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
3 6 1 2 3 4 5 12 3 2 3 4 3 1 2 3	6 0 4

Sample Input

Sample Output

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

6
0
4