B. Сделай сумму кратной 3
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальное количество ходов.

Пример
Входные данные
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
0
0
1
1
2
1
1
Примечание

В первом наборе входных данных, изначально $$$a = [2, 2, 5, 4]$$$. Один из оптимальных способов выполнения ходов:

  • удалить $$$4$$$-й элемент и получить $$$a = [2, 2, 5]$$$;
Таким образом сумма массива $$$a$$$ станет делиться на $$$3$$$ (действительно, $$$a_1 + a_2 + a_3 = 2 + 2 + 5 = 9$$$).

Во втором наборе входных данных изначально сумма массива равна $$$1+3+2 = 6$$$, что делится на $$$3$$$. Таким образом, ходы не требуются. Следовательно, ответ равен $$$0$$$.

В четвертом наборе входных данных изначально сумма массива равна $$$1$$$, что не делится на $$$3$$$. Удалением его единственного элемента вы получите пустой массив, поэтому его сумма равна $$$0$$$. Следовательно, ответ равен $$$1$$$.