CF1176B.Merge it!

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.

给你一个包含 $n$ 个整数 $a_1, a_2, \dots , a_n$ 的数组 $a$。

在一次操作中，你可以选择数组中的两个元素，并将它们替换为一个等于其和的新元素（新元素插入的位置无关紧要）。例如，从数组 $[2, 1, 4]$ 出发，你可以得到如下数组：$[3, 4]$、$[1, 6]$ 和 $[2, 5]$。

你的任务是：经过任意次（可能为零次）上述操作后，求数组中能被 $3$ 整除的元素的最大可能个数。

你需要回答 $t$ 个相互独立的查询。

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$).

第一行包含一个整数 $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$）。

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.

对于每个查询，在单独的一行中输出一个整数——在执行上述操作任意次（可能为零次）后，数组中能被 $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]$.

在示例的第一个查询中，你可以执行以下操作序列，从而得到 $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]$。