You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

陶陶有 $n$ 个橡皮泥，每个橡皮泥的体积为 $ai$ 。

陶陶是一个泥人巨匠，于是他可以进行以下操作：

每次操作选择两个橡皮泥，将其合并，新橡皮泥的体积为两个原体积之和，并将合成后的

橡皮泥插入原序列，当然插入的位置无关紧要。

例如，三个橡皮泥的体积为 $[2, 1, 4]$ ，陶陶能够获得 $[3, 4], [1, 6]$ 或 $[2, 5]$ 。

陶陶想知道经过若干次操作后，体积是 $3$ 的倍数的橡皮泥个数最多是多少个？

输入格式

第一行一个整数 $T$ 。

接下来 $T$ 组数据，每组数据第一行为一个整数 $n$ ，接下来一行有 $n$ 个整数，表示这 $n$ 个

橡皮泥的体积。

输出格式

对于每组数据，输出体积是 $3$ 的倍数的橡皮泥个数最多是多少个

输入样例

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

输出样例

3
3

数据范围

$1 ≤ T ≤ 1000$

$1 ≤ n ≤ 100$

$1 ≤ ai ≤ 10^9$