A. Мариса крадёт заказы Рейму
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Тьма, принесенная ласточкиным камнем — Естественная история
— Dateless Bar "Old Adam"

Мариса — девушка с принципами, она всегда помогает другим беречь их вещи. В течение $$$n$$$ дней она каждый день приходит и забирает обед для Рейму. $$$i$$$-й обед описывается своей вкусностью — целым числом $$$w_i$$$ ($$$0\le w_i\le 2$$$), образуя последовательность $$$w$$$ длины $$$n$$$.

Мариса особенно любит число $$$3$$$. Она может выполнить следующую операцию ноль или более раз:

  • Выбрать непустую подпоследовательность$$$^{\text{∗}}$$$ последовательности $$$w$$$, сумма элементов которой делится на $$$3$$$, и удалить элементы этой подпоследовательности из $$$w$$$.

Определите максимальное число операций, которое может выполнить Мариса.

$$$^{\text{∗}}$$$Последовательность $$$a$$$ является подпоследовательностью $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) элементов на произвольных позициях.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1\le n \le 100$$$).

Во второй строке даны $$$n$$$ целых чисел $$$w_1, w_2, \ldots, w_n$$$ ($$$0\leq w_i \leq 2$$$), обозначающие значения вкусности обедов.

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

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

Пример
Входные данные
3
4
0 0 0 0
3
1 2 0
5
1 2 1 2 1
Выходные данные
4
2
2
Примечание

В первом наборе входных данных Мариса может выполнить четыре операции: $$$$$$[\underline{0},0,0,0]\to[\underline{0},0,0]\to[\underline{0},0]\to[\underline{0}]\to [].$$$$$$

Во втором наборе входных данных Мариса может выполнить две операции: $$$$$$[\underline{1},\underline{2},0]- \gt [\underline{0}]- \gt [].$$$$$$

В третьем наборе входных данных Мариса может выполнить две операции: $$$$$$[\underline{1},2,1,\underline{2},1]- \gt [\underline{2},1,\underline{1}]- \gt [1].$$$$$$