A. Coins
time limit per test
7 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Baq has $$$n$$$ coins, each with a value of $$$m_{i}$$$. Baq does not like it when the machines where he buys subway tickets give him change, so he wants to know if with his $$$n$$$ coins he can pay exactly any amount.

What is the minimum amount of money that Baq cannot pay exactly with his $$$n$$$ coins?

Input

The input consists of an integer $$$t$$$ followed by $$$t$$$ cases.

Each case starts with an integer $$$n$$$ followed by the $$$n$$$ values of the coins, $$$m_{i}$$$.

Output

One line for each case with the minimum amount of money that Baq cannot pay exactly.

Scoring

$$$1 \leq t \leq 500$$$

$$$1 \leq m_{i} \leq 10^{9}$$$

$$$1 \leq n$$$

13 Points   $$$\; \; \; n \leq 10 $$$

26 Points   $$$\; \; \; n \leq 100$$$

30 Points   $$$\; \; \; n \leq 1000$$$

31 Points   $$$\; \; \; n \leq 10000$$$

Example
Input
3
5
2 4 16 8 1
3
1 2 3
4
3 5 7 1
Output
32
7
2