311094: CF1933B. Turtle Math: Fast Three Task

B. Turtle Math: Fast Three Tasktime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$.

Input

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$.

Output

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

ExampleInput

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

Output

1
0
0
1
1
2
1
1

Note

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_1, a_2, \ldots, a_n$。每次操作可以选择以下两种之一：
1. 从数组中移除一个元素，数组的长度减1；
2. 从数组中选取一个元素并将其值加1。

可以进行任意次数的操作。如果数组变为空，则无法再进行操作。任务是最小化操作次数，使得数组 $a$ 的元素和能被3整除。可能不需要任何操作。

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

输出数据格式：
对于每个测试用例，输出一个整数：所需的最小操作次数。

示例：
```
Input
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
Output
1
0
0
1
1
2
1
1
```

注意：
- 在第一个测试用例中，通过移除第四个元素，数组 $a$ 的元素和变为9，是3的倍数。
- 在第二个测试用例中，数组初始和为6，已经是3的倍数，所以不需要操作。
- 在第四个测试用例中，通过移除唯一的元素，得到一个空数组，其和为0，也是3的倍数。题目大意： 给定一个数组 $a_1, a_2, \ldots, a_n$。每次操作可以选择以下两种之一： 1. 从数组中移除一个元素，数组的长度减1； 2. 从数组中选取一个元素并将其值加1。 可以进行任意次数的操作。如果数组变为空，则无法再进行操作。任务是最小化操作次数，使得数组 $a$ 的元素和能被3整除。可能不需要任何操作。 输入数据格式： 第一行包含一个整数 $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$。 输出数据格式： 对于每个测试用例，输出一个整数：所需的最小操作次数。 示例： ``` Input 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 Output 1 0 0 1 1 2 1 1 ``` 注意： - 在第一个测试用例中，通过移除第四个元素，数组 $a$ 的元素和变为9，是3的倍数。 - 在第二个测试用例中，数组初始和为6，已经是3的倍数，所以不需要操作。 - 在第四个测试用例中，通过移除唯一的元素，得到一个空数组，其和为0，也是3的倍数。