CF1933B Turtle Math: Fast Three Task

给定一个数组 $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 翻译