We are talking about DTU here. Just like most engineering colleges in India, the gender ratio is pretty skewed at DTU. But the girls over here are very generous and noble. Many of them double date guys as a social service ;) .

Now its the valentines week, 11 at the night and "n" girls residing at the hostel are gossiping in the tv room of the hostel. Every girl is either dating a single person or double dating. These girls decide to confess, so they tell each other that whether they are dating a single guy or they are more noble and dating 2 guys. And mind you these are the noble girls of DTU, they NEVER LIE( at least no DTU girl  lies to other DTU girl ). But the hostel warden, Chameli, is interested in knowing the secret of the girls too.

So these girls decide to play a Game: Each of the "n" girls tell the warden the number of girls among the remaining n-1 girls who are double dating. You have to help the warden, Chameli, to figure out the total number of girls who are double dating.

Input

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

Each test case consists of 2 lines. The first line contains an integer n- number of girls at the hostel.

The next line contains n space separated integers. ith number denotes the number that the ith girl told the warden.

Output

Print the total number of girls who are double dating, or -1 if the girls are making a fool of the warden and the data is invalid, one test case per line.

T ≤ 100

2 ≤ n ≤ 10000

All of the n numbers are ≤ 10⁹

Example

Input:
1
3
2 2 2

Output:
3