Задан массив \(a\), состоящий из \(n\) целых чисел \(a_1, a_2, \dots , a_n\).
За одну операцию можно выбрать два элемента массива и заменить их на элемент, равный их сумме (не важно, куда в массиве вы вставите новый элемент). Например, из массива \([2, 1, 4]\) можно получить следующие массивы: \([3, 4]\), \([1, 6]\) и \([2, 5]\).
Можно произвести данную операцию произвольное (возможно, нулевое) количество раз.
Ваша задача — найти максимально возможное количество элементов, кратных \(3\), которые могут получиться в массиве после применения этой операции любое (возможно, нулевое) количество раз.
Требуется ответить на \(t\) независимых запросов.
Выходные данные
Для каждого запроса выведите ответ на отдельной строке — максимально возможное количество элементов, кратных \(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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5
3 1 2 3 1
7
1 1 1 1 1 2 2
|
3
3
|