A. Arithmetic Array 1537A

A. Arithmetic Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

An array b$b$ of length k$k$ is called good if its arithmetic mean is equal to 1$1$. More formally, if

b1+⋯+bkk=1.$$\frac{b_1+\cdots +b_k}{k}=1.$$

Note that the value b1+⋯+bkk$\frac{b_1+\cdots +b_k}{k}$ is not rounded up or down. For example, the array [1,1,1,2]$[1,1,1,2]$ has an arithmetic mean of 1.25$1.25$, which is not equal to 1$1$.

You are given an integer array a$a$ of length n$n$. In an operation, you can append a non-negative integer to the end of the array. What's the minimum number of operations required to make the array good?

We have a proof that it is always possible with finitely many operations.

Input

The first line contains a single integer t$t$ (1≤t≤1000$1\le t\le 1000$) — the number of test cases. Then t$t$ test cases follow.

The first line of each test case contains a single integer n$n$ (1≤n≤50$1\le n\le 50$) — the length of the initial array a$a$.

The second line of each test case contains n$n$ integers a1,…,an$a_1,\dots ,a_n$ (−104≤ai≤104$-{10}^4\le a_i\le {10}^4$), the elements of the array.

Output

For each test case, output a single integer — the minimum number of non-negative integers you have to append to the array so that the arithmetic mean of the array will be exactly 1$1$.

Example

input

Copy

4
3
1 1 1
2
1 2
4
8 4 6 2
1
-2

output

Copy

0
1
16
1

Note

In the first test case, we don't need to add any element because the arithmetic mean of the array is already 1$1$, so the answer is 0$0$.

In the second test case, the arithmetic mean is not 1$1$ initially so we need to add at least one more number. If we add 0$0$ then the arithmetic mean of the whole array becomes 1$1$, so the answer is 1$1$.

In the third test case, the minimum number of elements that need to be added is 16$16$ since only non-negative integers can be added.

In the fourth test case, we can add a single integer 4$4$. The arithmetic mean becomes −2+42$\frac{-2+4}{2}$ which is equal to 1$1$.

Solution is here:

1. #include<iostream>
2. using namespace std;
3. int main()
4. {
5. int t,n,j,sum=0;
6. int a[100];
7. cin>>t;
8. while(t--){
9. cin>>n;
10. for( j=0;j<n;j++)
11. {
12. cin>>a[j];
13. sum=sum+a[j];
14.  
15. }
16. if(sum<n )cout<<1<<endl;
17. else cout<<(sum)-n<<endl;
18. sum=0;
19. j=0;
20.  
21.  
22. } return 0;
23. }