Go Back

##### The National Anthem (200)

**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.

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 **A _{}**

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**.

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 (A_{1}, A_{2},.....A_{N}).

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 ≤ A_{i} ≤ 10^{6}

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.

Know more about Black Mirror: Bandersnatch here.