Go Back
The National Anthem (200)
Description

British prime minister Michael Callow is woken during the night to learn that Princess Susannah, a much-loved member of the Royal Family, has been kidnapped. For her safe return, the kidnappers demand that the Prime Minister must obtain a unique number S. The number can be obtained by performing the steps given below:

Say there are N numbers say A1, A2,.....,AN.
The prime minister has to make all of the numbers distinct. In order to do that, he can perform the following operation zero or more times:

  • Take any two numbers, say x and y from the given numbers.
  • The value of x shall remain as it is while the value of y is replaced by the sum x + y.


The special number is obtained by the addition of the minimum number of times the operation is required to be performed for each test case. Help Michael Callow rescue the beloved princess.

Input

The first line of input contains an integer T denoting the number of test cases.
The next line contains an integer N.
The next line contains N space separated integers (A1, A2,.....AN).

Output

Print 0 for those test cases where there is no operation performed.
Finally, on the last line, output the unique number S.

Constraints

1 ≤ T ≤ 10
1 ≤ N ≤ 100000
For each valid i, 1 ≤ Ai ≤ 106

Example
Copy Input

Input:
4
3
1 2 3
3
2 1 2
4
6 9 7 10
5
1 2 6 3 3

Output:
0
0
2

Explanation

Case 1:
No two numbers are the same. Therefore, number of times the operation is to be performed = 0. Hence, the output is ‘0’.

Case 2:
Take the second number (with value x = 1) and add it to the first number (with value x = 2). After adding, the sequence will be 3 1 2. Now the numbers are distinct. Therefore, minimum number of mixing operations that are required = 1.

Case 3:
No two numbers are the same. Therefore, number of times the operation is to be performed = 0. Hence, the output is ‘0’.

Case 4:
Take the fourth number (with value x = 3) and add it to the first number (with value x = 1). After adding, the sequence will be 1 2 6 4 3. Now the numbers are distinct. Therefore, minimum number of mixing operations that are required = 1.

Therefore, the unique number is = 0 + 1 + 0 + 1 = 2, and is printed on the final line.

Single Round Match #06
3 hour contest



Announcement
Scoring will be 100-200-250.
Know more about Black Mirror: Bandersnatch here.

Problem Tags
adhoc, maths

Supported by our Coding Partner