B. Объединяй!
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a$$$, состоящий из $$$n$$$ целых чисел $$$a_1, a_2, \dots , a_n$$$.

За одну операцию можно выбрать два элемента массива и заменить их на элемент, равный их сумме (не важно, куда в массиве вы вставите новый элемент). Например, из массива $$$[2, 1, 4]$$$ можно получить следующие массивы: $$$[3, 4]$$$, $$$[1, 6]$$$ и $$$[2, 5]$$$.

Можно произвести данную операцию произвольное (возможно, нулевое) количество раз.

Ваша задача — найти максимально возможное количество элементов, кратных $$$3$$$, которые могут получиться в массиве после применения этой операции любое (возможно, нулевое) количество раз.

Требуется ответить на $$$t$$$ независимых запросов.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество запросов.

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

Во второй строке каждого запроса записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots , a_n$$$ ($$$1 \le a_i \le 10^9$$$).

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

Для каждого запроса выведите ответ на отдельной строке — максимально возможное количество элементов, кратных $$$3$$$, которые могут получиться в массиве после применения описанной операции любое (возможно, нулевое) количество раз.

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

В первом запросе тестового примера Вы можете применить следующую последовательность операций, чтоб получить $$$3$$$ элемента, делящихся на $$$3$$$: $$$[3, 1, 2, 3, 1] \rightarrow [3, 3, 3, 1]$$$.

Во втором запросе Вы можете получить $$$3$$$ элемента, делящихся на $$$3$$$ при помощи следующей последовательности операций: $$$[1, 1, 1, 1, 1, 2, 2] \rightarrow [1, 1, 1, 1, 2, 3] \rightarrow [1, 1, 1, 3, 3] \rightarrow [2, 1, 3, 3] \rightarrow [3, 3, 3]$$$.