← 返回题目列表

Codeforces · 1933/B

B. 海龟数学:快速三项任务

中文机器翻译题面 查看原题

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

在一次移动中,您可以执行以下两种操作之一:

- 从数组中选择一个元素并将其从数组中删除。结果数组的长度减少了$$$1$$$;
- 从数组中选择一个元素并将其值增加 $$$1$$$。

您可以执行任意数量的移动。如果当前数组变空,则不能再进行任何移动。

你的任务是找到使数组 $$$a$$$ 的元素之和能被 $$$3$$$ 整除所需的最少移动次数。您可能需要 $$$0$$$ 移动。

请注意,空数组(长度为 $$$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$$$。

输出

对于每个测试用例,输出一个整数:最小移动次数。

示例

输入 #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

1
0
0
1
1
2
1
1

注意

在第一个测试用例中,最初数组 $$$a = [2, 2, 5, 4]$$$。采取行动的最佳方法之一是:

- 删除当前第 $$$4$$$ 个元素并得到 $$$a = [2, 2, 5]$$$;

在第二个测试用例中,最初,数组的总和为 $$$1+3+2 = 6$$$,可被 $$$3$$$ 整除。因此,不需要移动。因此,答案是$$$0$$$。

在第四个测试用例中,最初,数组的总和为$$$1$$$,它不能被$$$3$$$整除。通过删除其唯一元素,您将得到一个空数组,因此其总和为 $$$0$$$。因此,答案是$$$1$$$。