CRNVALEN - The Valentine Confession

no tags 

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 gossipping 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 no. 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^9

Example

Input:
1
3
2 2 2
Output:
3

hide comments
sanyam19: 2018-01-07 20:24:17

learned much from d observation.... :)
dont use unsigned long long int... it may give segmentation fault...better to use long long int
same as white hats.... :p

Last edit: 2018-01-07 20:24:48
ayushgupta1997: 2017-07-04 12:46:25

coded like a pro :)

gullu_mishra: 2015-09-16 21:23:27

little observation Can give you ....one time AC... :) .. nyc one ... learned how to observe a problm..

:.Mohib.:: 2015-07-14 17:36:45

Piece of cake... :)

anuveshkothari: 2015-07-14 08:33:17

check for case when all are zero..
cost me 2 W.A.

Akshat Mathur: 2015-06-26 11:28:57

AC in one go :-)

Amitayush Thakur: 2015-06-23 12:27:44

A few tricky cases otherwise an easy problem only!

harshit sharma: 2015-06-03 14:33:56

similar as WHITE HATS.. :)

mani_mckinnon: 2015-05-29 08:30:18

Good one.....

gamer496: 2015-05-19 02:26:44

much like many Indian engineering colleges


Added by:CSI
Date:2014-02-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64