给你一个数组 $$$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$$$。