You are given a number $n$ (divisible by $3$) and an array $a[1 \dots n]$. In one move, you can increase any of the array elements by one. Formally, you choose the index $i$ ($1 \le i \le n$) and replace $a_i$ with $a_i + 1$. You can choose the same index $i$ multiple times for different moves.

Let's denote by $c_0$, $c_1$ and $c_2$ the number of numbers from the array $a$ that have remainders $0$, $1$ and $2$ when divided by the number $3$, respectively. Let's say that the array $a$ has balanced remainders if $c_0$, $c_1$ and $c_2$ are equal.

For example, if $n = 6$ and $a = [0, 2, 5, 5, 4, 8]$, then the following sequence of moves is possible:

• initially $c_0 = 1$, $c_1 = 1$ and $c_2 = 4$, these values are not equal to each other. Let's increase $a_3$, now the array $a = [0, 2, 6, 5, 4, 8]$;
• $c_0 = 2$, $c_1 = 1$ and $c_2 = 3$, these values are not equal. Let's increase $a_6$, now the array $a = [0, 2, 6, 5, 4, 9]$;
• $c_0 = 3$, $c_1 = 1$ and $c_2 = 2$, these values are not equal. Let's increase $a_1$, now the array $a = [1, 2, 6, 5, 4, 9]$;
• $c_0 = 2$, $c_1 = 2$ and $c_2 = 2$, these values are equal to each other, which means that the array $a$ has balanced remainders.

Find the minimum number of moves needed to make the array $a$ have balanced remainders.

Input

The first line contains one integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($3 \le n \le 3 \cdot 10^4$) — the length of the array $a$. It is guaranteed that the number $n$ is divisible by $3$.

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 100$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $150\,000$.

Output

For each test case, output one integer — the minimum number of moves that must be made for the $a$ array to make it have balanced remainders.

见题面 Input 部分

见题面 Output 部分

The first test case is explained in the statements.

In the second test case, you need to make one move for $i=2$.

The third test case you need to make three moves:

• the first move: $i=9$;
• the second move: $i=9$;
• the third move: $i=2$.

In the fourth test case, the values $c_0$, $c_1$ and $c_2$ initially equal to each other, so the array $a$ already has balanced remainders.