← 返回题目列表

Codeforces · 2228/A

A. 魔理沙偷了灵梦的外卖

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

燕石自然史所带来的黑暗
— 无日期酒吧“老亚当”

玛丽莎是一个正直的女孩,总是帮助别人保护自己的财物。在 $$$n$$$ 天的时间里,她每天都会来灵梦的一份外卖。第 $$$i$$$ 外卖由其美味值来描述 - 一个整数 $$$w_i$$$ ($$$0\le w_i\le 2$$$),形成长度为 $$$n$$$ 的序列 $$$w$$$。

玛丽莎特别喜欢 $$$3$$$ 这个数字。她可以执行以下操作零次或多次:

  • 选择$$$w$$$的一个非空子序列$$$^{\text{*}}$$$,其总和能被$$$3$$$整除,并从$$$w$$$中删除该子序列的元素。

确定 Marisa 可以执行的最大操作数。

$$$^{\text{*}}$$$ 序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n \le 100$$$)。

第二行包含$$$n$$$整数$$$w_1, w_2, \ldots, w_n$$$ ($$$0\leq w_i \leq 2$$$),表示外卖的美味值。

输出

对于每个测试用例,输出 Marisa 可以执行的最大操作数。

示例

输入
复制

3
4
0 0 0 0
3
1 2 0
5
1 2 1 2 1

输出
复制

4
2
2

注意

在第一个测试用例中,Marisa 可以执行四种操作: $$[\underline{0},0,0,0]\to[\underline{0},0,0]\to[\underline{0},0]\to[\underline{0}]\to [].$$

在第二个测试用例中,Marisa 可以执行两个操作: $$[\underline{1},\underline{2},0]- \gt [\underline{0}]- \gt [].$$

在第三个测试用例中,Marisa 可以执行两个操作: $$[\underline{1},2,1,\underline{2},1]- \gt [\underline{2},1,\underline{1}]- \gt [1].$$