CF1933B.Turtle Math: Fast Three Task

You are given an array $a_1, a_2, \ldots, a_n$.

In one move, you can perform either of the following two operations:

• Choose an element from the array and remove it from the array. As a result, the length of the array decreases by $1$;
• Choose an element from the array and increase its value by $1$.

You can perform any number of moves. If the current array becomes empty, then no more moves can be made.

Your task is to find the minimum number of moves required to make the sum of the elements of the array $a$ divisible by $3$. It is possible that you may need $0$ moves.

Note that the sum of the elements of an empty array (an array of length $0$) is equal to $0$.

给你一个数组 $a_1, a_2, \ldots, a_n$。

每次操作，你可以执行以下两种操作之一：

• 从数组中选择一个元素并将其移除。操作后，数组长度减少 $1$；
• 从数组中选择一个元素，并将其值增加 $1$。

你可以执行任意次数的操作。若当前数组变为空，则无法再进行任何操作。

你的任务是求出使数组 $a$ 中所有元素之和能被 $3$ 整除所需的最少操作次数。可能需要 $0$ 次操作。

注意：空数组（长度为 $0$ 的数组）中所有元素之和定义为 $0$。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^4$).

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^4$）。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a single integer: the minimum number of moves.

对于每个测试用例，输出一个整数：最少移动次数。

In the first test case, initially the array $a = [2, 2, 5, 4]$. One of the optimal ways to make moves is:

• remove the current $4$th element and get $a = [2, 2, 5]$;

As a result, the sum of the elements of the array $a$ will be divisible by $3$ (indeed, $a_1 + a_2 + a_3 = 2 + 2 + 5 = 9$).

In the second test case, initially, the sum of the array is $1+3+2 = 6$, which is divisible by $3$. Therefore, no moves are required. Hence, the answer is $0$.

In the fourth test case, initially, the sum of the array is $1$, which is not divisible by $3$. By removing its only element, you will get an empty array, so its sum is $0$. Hence, the answer is $1$.

在第一个测试用例中，初始数组为 $a = [2, 2, 5, 4]$。一种最优的操作方式是：

• 删除当前第 $4$ 个元素，得到 $a = [2, 2, 5]$；

此时，数组 $a$ 中所有元素的和能被 $3$ 整除（事实上，$a_1 + a_2 + a_3 = 2 + 2 + 5 = 9$）。

在第二个测试用例中，初始数组的和为 $1+3+2 = 6$，该和已能被 $3$ 整除。因此无需任何操作，答案为 $0$。

在第四个测试用例中，初始数组的和为 $1$，不能被 $3$ 整除。删除其唯一元素后，将得到一个空数组，其和为 $0$。因此答案为 $1$。