Minimum Money to Donate

You are given t test cases. In each test case, you have n friends and a list of n integers representing the amount of money (in dollars) each friend currently has. Your task is to calculate the minimum amount of money that needs to be donated so that the total amount of money becomes divisible by n.

In mathematical terms, let \( S \) be the sum of money each friend has, and let \( n \) be the number of friends. You need to find the minimum non-negative integer \( x \) such that:

[ S + x \equiv 0 \pmod{n} ]

This can be computed as:

[ x = \begin{cases} 0, & \text{if } S \mod n = 0 \ n - (S \mod n), & \text{otherwise} \end{cases} ]

For example, consider a test case with n = 3 and a list of amounts [5, 2, 4]. The sum \( S = 11 \) and \( 11 \mod 3 = 2 \), so the minimum donation required is \( 3 - 2 = 1 \).

inputFormat

The first line of the input contains a single integer t, the number of test cases. The descriptions of the test cases follow.

For each test case:

• The first line contains an integer n, the number of friends.
• The second line contains n space-separated integers, where each integer represents the amount of money a friend has.

Note that the input is read from stdin.

outputFormat

For each test case, output a single integer on a new line representing the minimum amount of money needed to be donated. The output is printed to stdout.

## sample

3
3
5 2 4
4
3 3 3 3
2
7 1

1
0
0

</p>