Statement : A. 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.

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.

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

Input

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

Output

4
2
2

Note

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].$$$