CF2228A Marisa Steals Reimu's Takeout

燕石博物志所带来的黑暗 ——旧约酒场

Marisa 是个正直的女孩，总是帮别人看管好东西。在连续的 $n$ 天里，她每天都会来拿走 Reimu 的一个外卖。第 $i$ 个外卖有一个美味值——一个整数 $w_i$（$0\le w_i\le 2$），组成了一个长度为 $n$ 的序列 $w$。 Marisa 对数字 $3$ 有种特别的喜爱。她可以执行以下操作任意次（包括零次）： - 选出 $w$ 中一个非空的子序列 $^{*}$，且该子序列元素和能被 $3$ 整除，然后把这个子序列从 $w$ 中移除。 请你帮忙算算，Marisa 最多能执行多少次这样的操作。 $^{*}$ 序列 $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 能执行的最大操作次数。

## 样例解释 第一组测试中，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] \to [\underline{0}] \to [].$ 第三组测试中，Marisa 最多可以执行两次操作： $[\underline{1},2,1,\underline{2},1] \to [\underline{2},1,\underline{1}] \to [1].$