Codeforces Round 929 (Div. 3) |
---|
Finished |
You are given an array $$$a_1, a_2, \ldots, a_n$$$.
In one move, you can perform either of the following two operations:
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.
842 2 5 431 3 243 7 6 81142 2 4 225 572 4 8 1 9 3 424 10
1 0 0 1 1 2 1 1
In the first test case, initially the array $$$a = [2, 2, 5, 4]$$$. One of the optimal ways to make moves is:
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$$$.
Name |
---|