CF2228A.Marisa Steals Reimu's Takeout

The Darkness Brought In by Swallowstone Naturalis Historia

— Dateless Bar "Old Adam"

Marisa is a girl of integrity who always helps others safeguard their belongings. Over a period of $n$ days, she comes each day to take one of Reimu's takeouts. The $i$-th takeout is described by its deliciousness value — an integer $w_i$ ($0\le w_i\le 2$), forming a sequence $w$ of length $n$.

Marisa has a special fondness for the number $3$. She can perform the following operation zero or more times:

• Select a non-empty subsequence$^{\text{∗}}$ of $w$ whose sum is divisible by $3$, and remove the elements of the subsequence from $w$.

Determine the maximum number of operations Marisa can perform.

$^{\text{∗}}$A sequence $a$ is a subsequence of a sequence $b$ if $a$ can be obtained from $b$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

由燕石带来的黑暗——《自然史》

——无日期酒吧“老亚当”

玛莉莎是一位正直的女孩，总是帮助他人守护物品。在连续 $n$ 天中，她每天都会来取走灵梦的一份外卖。第 $i$ 份外卖以其美味值（一个整数 $w_i$，满足 $0 \le w_i \le 2$）来描述，从而构成一个长度为 $n$ 的序列 $w$。

玛莉莎对数字 $3$ 情有独钟。她可以执行以下操作零次或多次：

• 选取 $w$ 的一个非空子序列$^{\text{∗}}$，其元素之和能被 $3$ 整除，并将该子序列中的所有元素从 $w$ 中移除。

请确定玛莉莎最多能执行多少次这样的操作。

$^{\text{∗}}$ 序列 $a$ 是序列 $b$ 的一个子序列，当且仅当 $a$ 可通过从 $b$ 的任意位置删除若干个（可能为零个或全部）元素而得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1\le n \le 100$).

The second line contains $n$ integers $w_1, w_2, \ldots, w_n$ ($0\leq w_i \leq 2$), denoting the deliciousness values of the takeouts.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$），表示各外卖的美味值。

For each test case, output the maximum number of operations Marisa can perform.

对于每个测试用例，输出 Marisa 能执行的最大操作次数。

In the first test case, Marisa can perform four operations: $$[\underline{0},0,0,0]\to[\underline{0},0,0]\to[\underline{0},0]\to[\underline{0}]\to [].$$

In the second test case, Marisa can perform two operations: $$[\underline{1},\underline{2},0]- \gt [\underline{0}]- \gt [].$$

In the third test case, Marisa can perform two operations: $$[\underline{1},2,1,\underline{2},1]- \gt [\underline{2},1,\underline{1}]- \gt [1].$$

在第一个测试用例中，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].$$