给定一个数组 $$$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$$$ 整除的元素的最大可能数量。
示例
输入 #1
2 5 3 1 2 3 1 7 1 1 1 1 1 2 2
输出 #1
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]$$$。