CRNVALEN - The Valentine Confession

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 ≤ 109

Example

Input:
1
3
2 2 2

Output:
3

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

hide comments
2015-05-18 17:43:11 Insomniac
confession (y) ......

Last edit: 2015-05-18 17:43:35
2015-05-13 12:39:38
i am getting SIGFPE .i don't know why.can anyone help??
2015-02-09 13:06:01 Daksh
Happy Valentine's Day to everyone ;) in advance :)

Last edit: 2015-02-09 13:06:37
2014-03-18 19:09:26 Ritam Shukla
Kudos for writing misleading problem statement!! "Every girl is either dating a single person or double dating." Regardless of whether the girls are lying or not, the setter should not lie to the solvers...

reply(CSI) -> Out of the 180+ solvers you are the first one who could not comprehend the problem in a correct way, i still cant find how and where the problem was misleading.The problem statement is correct. Maybe you should re-read the problem a couple of times so that you dont make any mistakes.

Last edit: 2014-03-21 13:14:13
2014-03-04 15:10:40 californiagurl
i have solved similar questions before,, but this one is escaping me
EDIT: that one stupid test case gave me so many WAs... i guess i didn't expect those girls to be honest and faithful to their guys at the same time...too good to be true,, JK ;)

Last edit: 2014-03-08 04:58:53
2014-02-21 16:59:19 CSI
@californiagurl yes you are right
2014-02-17 15:13:18 californiagurl
if i'm right, we print -1 if any of the girls are caught lying,is that so?
@CSI plz check my code 11084544

Last edit: 2014-02-18 04:57:37
2014-02-11 20:05:40 RIVU DAS
Happy Valentine's Day to everyone!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.