You are the organizer of a Wizarding Duel tournament at Hogwarts. N players participated in the tournament and each player played with every other player exactly once, and each such game resulted in a winner and a loser (no drawn games). It is now time to declare the results. Each player's score is the number of games the player won. However, you realize that something possibly went wrong with the scoring system, and the scores that you have noted down might be wrong. In fact, the scores you have noted down could simply not be possible. For example, suppose there are 3 players and the scores that you noted are 0,0 and 2. Clearly this is not possible as the game between the first two players must have had a winner and thus both the players cannot have score 0.
While you have no way to figure out the correct scores of each player, you've decided to set the scores right by adjusting the scores of some players. The new set of scores should be possible to have arisen in the tournament, otherwise there would be ample proof that the scoring is wrong. However, making drastic changes might cause suspicion. So you've decided to adjust the scores so that the sum of the absolute differences between the old and the new scores of each player is minimized. In other words, if the original scores which you noted are a1,..,aN, you must change them to the series of possible scores b1,...bN such that the sum |ai - bi| is minimized.
Input (STDIN):
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by the set of scores which you have noted down: a1..aN.
Output (STDOUT):
Output T lines, one for each test case, containing the minimum sum of absolute values in order to make the scorecard a valid one.
Constraints:
1 <= T <= 20
2 <= N <= 50
0 <= ai <= 100
Time Limit: 3 seconds
Memory Limit: 64 MB
Sample Input:
2
3
0 0 2
5
5 3 2 1 4
Sample Output:
1
5
You are the organizer of a Wizarding Duel tournament at Hogwarts. N players participated in the tournament and each player played with every other player exactly once, and each such game resulted in a winner and a loser (no drawn games). It is now time to declare the results. Each player's score is the number of games the player won. However, you realize that something possibly went wrong with the scoring system, and the scores that you have noted down might be wrong. In fact, the scores you have noted down could simply not be possible. For example, suppose there are 3 players and the scores that you noted are 0,0 and 2. Clearly this is not possible as the game between the first two players must have had a winner and thus both the players cannot have score 0.
While you have no way to figure out the correct scores of each player, you've decided to set the scores right by adjusting the scores of some players. The new set of scores should be possible to have arisen in the tournament, otherwise there would be ample proof that the scoring is wrong. However, making drastic changes might cause suspicion. So you've decided to adjust the scores so that the sum of the absolute differences between the old and the new scores of each player is minimized. In other words, if the original scores which you noted are a1,..,aN, you must change them to the series of possible scores b1,...bN such that the sum |ai - bi| is minimized.
Input (STDIN):
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by the set of scores which you have noted down: a1..aN.
Output (STDOUT):
Output T lines, one for each test case, containing the minimum sum of absolute values in order to make the scorecard a valid one.
Constraints:
1 <= T <= 20
2 <= N <= 50
0 <= ai <= 100
Sample Input:
2
3
0 0 2
5
5 3 2 1 4
Sample Output:
1
5
