题目描述

给定一个整数 $n$（保证 $n$ 能被 $3$ 整除）和一个数组 $a[1 \dots n]$。每次操作，你可以将数组中的任意一个元素加 $1$。具体来说，你可以选择一个下标 $i$（$1 \le i \le n$），并将 $a_i$ 替换为 $a_i + 1$。同一个下标 $i$ 可以被多次选择进行操作。

我们用 $c_0$、$c_1$ 和 $c_2$ 分别表示数组 $a$ 中除以 $3$ 余数为 $0$、$1$ 和 $2$ 的元素个数。如果 $c_0$、$c_1$ 和 $c_2$ 三者相等，则称数组 $a$ 的余数是平衡的。

例如，如果 $n = 6$，$a = [0, 2, 5, 5, 4, 8]$，则可以进行如下操作：

• 初始时 $c_0 = 1$，$c_1 = 1$，$c_2 = 4$，三者不相等。将 $a_3$ 加 $1$，此时 $a = [0, 2, 6, 5, 4, 8]$；
• 此时 $c_0 = 2$，$c_1 = 1$，$c_2 = 3$，三者仍不相等。将 $a_6$ 加 $1$，此时 $a = [0, 2, 6, 5, 4, 9]$；
• 此时 $c_0 = 3$，$c_1 = 1$，$c_2 = 2$，三者仍不相等。将 $a_1$ 加 $1$，此时 $a = [1, 2, 6, 5, 4, 9]$；
• 此时 $c_0 = 2$，$c_1 = 2$，$c_2 = 2$，三者相等，说明数组 $a$ 的余数已经平衡。

请你求出使数组 $a$ 的余数平衡所需的最少操作次数。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来每个测试用例包含两行：

第一行包含一个整数 $n$（$3 \le n \le 3 \cdot 10^4$），表示数组 $a$ 的长度。保证 $n$ 能被 $3$ 整除。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq 100$）。

保证所有测试用例中 $n$ 的总和不超过 $150\,000$。

输出格式

对于每个测试用例，输出一个整数，表示使数组 $a$ 的余数平衡所需的最少操作次数。

说明/提示

第一个测试用例的过程已在题目描述中给出。

第二个测试用例，你需要对 $i=2$ 进行一次操作。

第三个测试用例，你需要进行三次操作：

• 第一次操作：$i=9$；
• 第二次操作：$i=9$；
• 第三次操作：$i=2$。

第四个测试用例，$c_0$、$c_1$ 和 $c_2$ 初始时就相等，因此数组 $a$ 已经是余数平衡的。

由 ChatGPT 4.1 翻译

样例

4
6
0 2 5 5 4 8
6
2 0 2 1 0 0
9
7 1 3 4 2 10 3 9 6
6
0 1 2 3 4 5

3
1
3
0