← 返回题目列表

Codeforces · 1176/B

B. 合并吧!

中文机器翻译题面 查看原题

给定一个数组 $$$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]$$$。