Minimum Operations to Make Array Elements Distinct

You are given an array of integers and your task is to compute the minimum number of operations required to make all the elements in the array distinct. In each operation, you can increment any element by one. This must be done for multiple test cases.

Hint: A good strategy is to sort the array and then for every element (starting from the second), if it is not strictly larger than its predecessor, increase it to be one greater than the previous element. The total amount added across all operations is the answer for that test case.

Formally, if we denote the sorted array as \(a_1, a_2, \ldots, a_n\), then for every \(i\) from 2 to \(n\), if \(a_i \leq a_{i-1}\), you must perform \(a_{i-1} + 1 - a_i\) operations on \(a_i\) so that it becomes \(a_{i-1} + 1\).

inputFormat

The first line of the input contains an integer \(T\) representing the number of test cases.

Each test case consists of two lines. The first line contains an integer \(n\), the size of the array. The second line contains \(n\) space-separated integers denoting the elements of the array.

outputFormat

For each test case, output a single line containing the minimum number of operations required to make all the array elements distinct.

## sample

1
3
1 2 2

1

</p>