A11300 | Turtle Math: Fast Three Task

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

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

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