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.

Input

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.

Output

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

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