candy-1_9747
Daenerys Targaryen set her eyes on The Kingdom of The North which is ruled by the House Stark. There is a huge market in the Castle of Winterfell that sells products of all prices starting from 1 coin i.e. there are products worth Rs 1, 2, 3 . . .  10^17 .

Ned Stark is the Lord of Winterfell. He gives Daenerys some coins. Each coin has its own denomination (in Rs). The coins need not be of distinct denomination. He asks Daenerys to predict the cheapest product that she will not be able to buy from the market using the coins given to her. If she can correctly predict it, she'll win the Castle of Winterfell and hence conquer one kingdom successfully. 

If she can buy all products from the market (i.e all products upto price Rs 10^17 ), then output -1.

You're appointed as her advisor after she sent away Ser Jorah Mormont. So you need to solve the problem for her.

Input

The first line contains T, the number of test cases.

The first line of each test case contains an integer N denoting the number of coins Daenerys has.

The next line contains N space separated integers indicating the denominations of the coins (A_i).

Output

The only line of output should contain 1 integer denoting the price of the cheapest product that she cannot buy. If she can buy all the products, then this line contains -1.

Constraints

1 ≤ T ≤ 100

1 ≤ N ≤ 10^5

1 ≤ A_i ≤ 10^9 for i = 1, 2, .., N

Warning

Large I/O files. Use scanf/printf instead of cin/cout or else use ios::sync_with_stdio(false).

Note

Partial marks are awarded if any test case passes.

SAMPLE INPUT
2
10
1 2 4 8 16 32 64 128 256 512
5
1 3 4 5 7

SAMPLE OUTPUT
1024
2

Explanation

In the first test case, Daenerys can buy all items upto 1023 since the coins available with her are powers of 2 (in other words binary place values). 

In the second test case, Daenerys needs Rs 2 coin in order to buy the Rs 2 product.
t = input()
ls = 10**17
for _ in xrange(t):
    n = input()
    num = [int(i) for i in raw_input().split()]
    num.sort()
    x = 0
    for i in num:
        if(i<=x+1):
            x+=i
    x+=1
    if(x>ls):
        print -1
    else:
        print x
2
10
1 2 4 8 16 32 64 128 256 512
5
1 3 4 5 7

SAMPLE 2
10
1 2 4 8 16 32 64 128 256 512
5
0 3 4 5 7

SAMPLE 2
10
1 2 0 8 16 32 64 128 256 512
5
1 3 4 5 7

SAMPLE 2
10
1 2 4 8 11 32 64 128 256 512
6
0 3 4 5 0

SAMPLE 2
11
1 2 6 8 11 32 64 128 256 512
6
0 3 4 5 0

SAMPLE 2
10
1 2 1 8 16 32 64 128 611 512
5
1 3 4 5 7

SAEPLL 2
10
1 2 0 8 29 2 64 128 206 512
5
1 3 4 5 7

SAEPLL 2
10
1 2 0 8 29 2 64 128 206 512
5
1 1 4 5 7

SAEPLL 2
10
1 2 0 6 29 2 64 128 206 512
5
1 1 4 5 7

SAEPLL 2
10
0 2 0 6 29 2 64 128 206 512
2
1 1 4 5 7

LLPEAS 2
10
0 2 0 6 29 2 64 128 206 0
2
1 0 4 5 7

LLPEAS 2
20
0 2 1 6 29 2 64 191 206 0
2
1 0 8 5 7

LSPEAL 2
8
0 1 2 10 29 1 79 67 65 0
2
1 1 10 10 14

LSPEAL 2
8
0 0 2 1 5 1 153 57 59 0
2
1 0 7 13 6

LSPEAL 2
10
1 2 4 8 16 32 64 128 256 756
5
1 3 4 5 7

SAMPLE 2
10
0 2 4 8 16 32 64 128 256 512
6
0 3 4 5 7

SAMPLE 2
10
1 0 0 8 16 32 64 128 427 512
5
1 3 4 5 7

SAEPLM 2
10
1 2 4 8 11 32 64 128 256 512
6
-1 3 4 5 0

SAMPLE 2
10
1 2 -1 8 29 32 64 128 124 512
5
1 3 4 5 7

SAEPLL 2
10
1 2 0 8 29 2 64 128 206 512
5
2 3 4 5 7

SAEPLL 2
10
-1 2 0 6 29 2 64 128 206 0
2
1 1 4 5 7

LLPEAS 2
8
0 0 2 10 29 1 79 67 65 0
2
1 1 10 10 14

LSPEAL 2
8
0 0 2 1 5 1 153 57 6 0
2
1 0 7 13 6

LSPEAL 2
8
0 0 2 2 5 1 153 57 59 0
2
1 0 7 13 6

LAEPSL 2
11
1 2 6 8 3 32 64 128 256 512
6
0 3 4 5 0

ELPMAS 2
20
1 2 2 6 29 1 51 119 206 0
2
1 1 8 10 7

LSPEAL 2
8
0 2 2 2 29 1 79 67 65 0
2
1 1 10 10 14

LSPEAL 2
8
0 0 2 -1 5 1 276 57 59 0
2
0 0 7 13 6

LAEPSL 2
10
1 2 3 8 16 32 64 128 256 512
5
0 3 4 5 10

SAMPLE 2
10
1 0 0 8 16 32 64 128 427 512
5
1 3 1 7 7

SAEPLM 2
11
1 1 2 8 11 32 64 128 256 812
6
0 3 4 5 0

SAMPLE 2
11
0 2 6 8 12 46 64 128 1 512
6
-1 3 1 0 0

ELPMAS 2
39
0 4 2 6 29 0 51 191 206 1
2
1 0 8 5 7

LSPEAL 2
20
0 0 2 6 29 -1 51 119 206 -1
2
1 0 8 10 7

LSPEAL 2
20
2 2 2 6 29 1 51 119 206 0
2
1 1 8 10 7

LSPEAL 2
8
0 1 2 8 29 1 50 23 65 0
2
2 1 10 6 14

LSPEAL 2
10
1 3 3 8 16 32 64 128 256 512
5
0 3 4 5 10

SAMPLE 2
10
1 2 4 8 11 32 25 128 256 30
6
-1 3 2 5 0

SAMPLE 2
11
0 2 6 4 12 46 64 128 1 512
6
-1 3 1 0 0

ELPMAS 2
10
2 1 0 6 29 2 5 128 0 512
2
1 1 4 5 7

LLPEAS 2
10
0 2 0 6 29 2 64 128 206 0
2
-1 0 7 5 7

SLPEAL 2
34
1 2 0 6 29 2 64 191 206 0
2
1 -1 8 5 7

LEPSAL 2
20
0 4 2 1 29 0 51 143 206 0
2
1 0 8 10 7

LSPFAL 2
8
1 3 2 6 29 0 51 119 206 0
2
2 1 14 10 7

LSPEAL 2
8
0 2 2 2 0 1 79 67 65 1
2
1 1 10 10 14

LSPEAL 2
10
1 2 4 8 11 32 25 128 256 57
6
-1 3 2 5 0

SAMPLE 2
16
1 2 2 6 29 0 51 119 320 0
2
2 0 8 9 7

LSPEAL 2
8
0 0 2 1 4 0 153 57 79 1
2
1 0 7 13 6

LSPEAL 2
8
1 0 2 0 5 0 153 57 59 0
2
2 1 12 13 6

LAEPSL 2
10
0 0 0 6 29 1 64 128 206 0
2
-1 0 7 5 7

SLPEAL 2
10
1 2 4 8 11 61 25 128 256 57
6
-1 3 2 8 0

SAMPLE 2
10
0 1 0 6 29 2 3 128 310 0
2
3 -1 8 4 7

LSPEAL 2
20
0 2 -1 12 25 2 59 191 206 0
2
1 -1 8 12 3

LSPEAL 2
20
0 0 2 6 29 -1 88 119 206 -1
2
2 0 8 3 7

LSQEAL 2
8
0 2 2 11 29 1 51 67 112 1
2
0 1 10 10 14

LSPEAL 2
10
1 1 0 8 16 64 64 184 256 4
5
1 3 4 5 3

SAEPLL 2
10
0 1 0 4 29 2 3 128 310 0
2
3 -1 8 4 7

LSPEAL 2
20
0 2 -1 12 25 2 59 191 206 -1
2
1 -1 8 12 3

LSPEAL 2
20
0 4 2 1 29 0 79 143 345 0
2
1 -1 8 10 7

LSPEAL 2
8
1 2 3 11 65 0 0 29 206 0
2
1 1 10 10 14

LSPEAL 2
8
0 1 2 15 29 2 79 69 122 0
2
2 -1 3 10 12

LSPEAL 2
9
0 0 1 6 29 1 64 128 206 0
2
-1 0 7 5 14

SLPEAL 2
20
0 -1 2 6 29 -1 88 119 206 -1
2
2 0 8 3 7

LSQEAL 2
8
0 0 2 10 52 1 126 48 65 -1
2
1 2 10 10 32

KSPEAL 2
8
-2 2 3 8 55 1 79 34 65 -1
2
1 0 6 10 6

LSPEAL 2
10
2 1 0 8 16 52 64 184 256 4
5
1 3 4 5 3

SAEPLL 2
10
1 2 4 8 14 61 25 128 256 57
6
-1 3 2 10 1

SAMPLE 2
34
1 2 0 11 14 2 98 191 324 0
2
1 -2 8 5 2

LEPSAL 2
12
0 2 0 11 8 0 -1 119 206 -1
4
1 1 10 10 7

LSPAEL 2
8
1 2 3 11 65 0 0 29 206 0
2
2 1 10 10 19

LSPEAL 2
10
2 1 1 8 16 52 64 184 256 4
5
1 3 4 5 3

SAEPLL 2
10
1 0 0 15 28 31 151 463 427 512
5
1 3 2 7 7

SAEPLM 2
10
0 1 0 4 29 2 3 66 310 0
1
3 -2 8 4 7

LSPEAL 2
12
0 2 0 11 8 0 -1 119 206 -1
4
2 1 10 10 7

LSPAEL 2
10
2 2 1 8 16 52 64 184 256 4
5
1 3 4 5 3

SAEPLL 2
10
1 0 0 1 28 31 151 463 427 512
5
1 3 2 7 7

SAEPLM 2
10
1 2 4 8 9 32 100 128 611 198
5
1 3 5 8 7

SBEPLL 2
2
1 2 -1 14 29 62 116 128 124 512
5
2 4 1 7 3

SAEPLL 2
10
2 2 1 8 16 52 64 184 256 4
5
1 3 1 5 3

SAEPLL 2
10
1 2 4 8 14 61 25 38 256 57
2
-1 0 2 10 1

SAMPLE 2
10
1 2 4 8 9 32 100 128 611 198
5
1 3 5 8 2

SBEPLL 2
2
1 2 -1 14 29 62 143 128 124 512
5
2 4 1 1 3

SAEPLL 2
35
-2 2 2 4 44 1 36 191 206 0
2
1 -2 16 8 6

LSQEAL 2
11
0 2 1 15 29 1 51 67 112 2
2
-1 1 10 3 25

LSPEAL 2
10
1 2 4 8 14 61 25 38 256 35
4
-1 0 2 10 1

SAMPLE 2
5
1 2 0 2 9 2 64 128 256 299
5
0 0 5 9 0

SAMPLE 2
10
1 1 0 4 29 2 3 66 37 0
1
3 -2 8 4 7

KAEPSL 2
16
-2 1 -1 6 0 2 111 128 206 0
3
1 0 8 1 7

LSPEAL 2
17
1 0 1 1 31 1 93 010 59 0
2
2 -1 7 13 9

PSLEAL 2
10
1 2 4 8 14 61 25 38 256 35
4
0 0 2 10 1

SAMPLE 2
10
1 2 4 8 14 2 25 38 256 35
4
0 0 2 10 1

SAMPLE 2
2
1 2 -1 25 29 62 143 128 124 641
5
4 4 1 1 3

SAEPLL 2
10
0 1 0 4 29 2 3 8 37 0
1
4 -2 8 4 7

KAEPSL 2
10
1 2 4 8 14 3 25 38 256 35
4
0 0 2 10 1

SAMPLE 2
10
0 1 0 4 29 2 3 8 37 1
1
4 -2 8 4 7

KAEPSL 2
2
1 2 -2 25 29 62 143 128 124 748
5
4 4 1 1 3

SAEPLL 2
10
1 2 4 8 16 32 64 128 256 512
6
0 3 4 5 7

SAMPLE 2
10
1 2 0 8 16 32 64 128 256 512
5
1 3 4 5 7

SAEPLM 2
10
1 2 4 8 16 32 64 128 256 512
6
0 3 4 5 0

SAMPLE 2
10
1 2 0 8 16 32 64 128 427 512
5
1 3 4 5 7

SAEPLM 2
10
1 2 0 8 16 32 64 128 611 512
5
1 3 4 5 7

SAEPLM
1024
2 1024
1
 4
2
 27
1
 4
1
 5
2
 6
2
 6
3
 12
3
 1
3
 1
2
 12
2
 5
3
 10
2
 512
2
 1
1
 2
2
 27
0
 0
2
 6
1
 0
3
 4
3
 16
2
 11
2
 21
1
 13
3
 8
3
 0
1
 7
1
 2
6
 5
1
 4
0
 14
2
 -1
2
 14
3
 5
4
 2
1
 114
0
 26
0
 17
3
 1
0
 12
0
 8
2
 13
4
 9
3
 525
0
 12
1
 9
2
 4
4
 2
0
 52
0
 13
0
 0
0
 -1
1
 7
2
 3
2
 11
0
 -1
0
 8
0
 7
3
 6
0
 3
0
 -2
1
 0
4
 -2
2
 32
2
 55
0
 6
-1
 -1
3
 7
4
 33
2
 2
21
 11
-1
 -1
4
 34
2
 3
21
 25
2
 0
18
 34
14
 211
0
 25
20
 0
12
 -1
-1
 7
0
 189
0
 8
1
 12
-1
 -2
3
 5
0
 189
4
 130
4
 0
14
 19
-1
 131
4
 20
-1
 -1
14
 1024
1
 4
2
 1024
1
 4
2
 4
2
