URI Online Judge | 3007

Lucas and Frobenius

By Paulo E. D. Pinto, Universidade do Estado do Rio de Janeiro BR Brazil

Timelimit: 3

Lucas has a lot of tokens with integer values ​​stamped on them. He started playing with tokens containing only values ​​3 and 7 and realized that he could collect tokens to make a total of 3, 6, 7, 9, 10, 12,13, 14, etc., but could not form sets whose sum was 4 , 5, 8 or 11. He wondered if 11 would be the largest sum for which such sets could not be formed. Well, the german mathematician Frobenius had already solved this problem for 2 types of values ​​and 11 is really the right answer for this case. Given the value tokens a and b, this problem can only be solved when MDC (a, b) = 1 and the largest sum that cannot be obtained is given by     a * b-(a+b). But the problem is still open when you have more than two types of values. Write a program to help Lucas find the largest sum that can't be obtained using up to 10 different token types.

Input

The input consists of many tests. The first line contains the number of test cases, an integer n (1 ≤ n ≤ 20),  The next n lines contain, each one, a test case. The first integer int each line, q (2 ≤ q ≤ 10), indicates how many different kinds of tokens exist. This number is followed by q integers pi ( 2 ≤  pi  ≤ 1000), the values of the tokens.

Output

For each test case print, in one line, the maximum sum that can not be obtained with the kinds of tokens given. If this value is unlimited or greater than 1,000,000, print -1.

Input Sample Output Sample

3

2 3 7

3 46 66 78

2 995 997

11

-1

990023