Merge it!

你有一个长度为$n$的数组$a_1,a_2,\dots,a_n$。 每一次操作，你可以选择两个元素，并且用它们的和来代替这两个元素（无论在何处插入都没有影响）。比如，如果$a=\{2,1,4\}$，那么你可以得到如下几种数组：$\{3,4\},\{1,6\},\{2,5\},\{7\}$。 你的任务是通过若干次操作，使得这个序列中能被$3$整除的元素尽可能多。 多测，共有$t$组询问。

You are given an array $ a $ consisting of $ n $ integers $ a_1, a_2, \dots , a_n $ . In one operation you can choose two elements of the array and replace them with the element equal to their sum (it does not matter where you insert the new element). For example, from the array $ [2, 1, 4] $ you can obtain the following arrays: $ [3, 4] $ , $ [1, 6] $ and $ [2, 5] $ . Your task is to find the maximum possible number of elements divisible by $ 3 $ that are in the array after performing this operation an arbitrary (possibly, zero) number of times. You have to answer $ t $ independent queries.

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of queries. The first line of each query contains one integer $ n $ ( $ 1 \le n \le 100 $ ). The second line of each query contains $ n $ integers $ a_1, a_2, \dots , a_n $ ( $ 1 \le a_i \le 10^9 $ ).

For each query print one integer in a single line — the maximum possible number of elements divisible by $ 3 $ that are in the array after performing described operation an arbitrary (possibly, zero) number of times.

2
5
3 1 2 3 1
7
1 1 1 1 1 2 2

3
3

In the first query of the example you can apply the following sequence of operations to obtain $ 3 $ elements divisible by $ 3 $ : $ [3, 1, 2, 3, 1] \rightarrow [3, 3, 3, 1] $ . In the second query you can obtain $ 3 $ elements divisible by $ 3 $ with the following sequence of operations: $ [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] $ .