题目描述

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

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

• 从数组中选择一个元素并将其移除。这样，数组的长度减少 $1$；
• 从数组中选择一个元素，并将其值加 $1$。

你可以进行任意次数的操作。如果当前数组为空，则不能再进行任何操作。

你的任务是求出使数组 $a$ 的元素和能够被 $3$ 整除所需的最小操作次数。可能不需要进行任何操作。

注意，空数组（长度为 $0$ 的数组）的元素和等于 $0$。

输入格式

输入的第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一个整数，表示所需的最小操作次数。

说明/提示

在第一个测试用例中，初始数组 $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$。

由 ChatGPT 4.1 翻译

样例

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

1
0
0
1
1
2
1
1