玛丽莎是一个正直的女孩,总是帮助别人保护自己的财物。在 $$$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 可以执行的最大操作数。
示例
输入复制
340 0 0 031 2 051 2 1 2 1
输出复制
422
注意
在第一个测试用例中,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].$$