「SvR-2」1+2=3

你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $0,1,2$，你要将所有木棒拼起来，使相邻的数和为 $3$ 的对数最大。 例如，$1\text{ - }2$ 和 $1\text{ - }0$ 两个木棒，如果按 $1\text{ - }0,1\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\text{ - }{\underline\color{red}\textbf2},{\underline\color{red}\textbf1}\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$，因为 $2+1=3$。

**本题有多组数据。** 输入的第一行一个正整数表示数据组数 $T$。 对于每组数据，一行 $9$ 个非负整数，分别表示 $0\text{ - }0,0\text{ - }1,0\text{ - }2,1\text{ - }0,1\text{ - }1,1\text{ - }2,2\text{ - }0,2\text{ - }1,2\text{ - }2$ 型木棒的个数。

$T$ 行，每行一个整数表示答案。

3
4 1 3 4 7 7 9 10 3
6 3 6 4 3 4 5 6 6
6 10 7 1 4 2 6 4 2

31
23
19

#### 数据规模与约定 对于全部数据，保证 $1\le T\le 10^5$，记 $a_{i,j}$ 表示 $i\text-j$ 木棒的个数，保证 $0\le a_{i,j}\le 10^9$。 **本题自动开启捆绑测试和 O2 优化。** 记 $sum$ 表示一个测试点中所有数据的所有 $a_{i,j}$ 之和。 | Subtask | $T$ | $sum$ | 特殊性质 |分值 | | :------: | :------: | :------: | :------: | :------: | | $1$ | $1 \leq T \leq 10$ | $1\le sum\le 10$ |无| $10 \operatorname{pts}$ | | $2$ | $1 \leq T \leq 50$ | $1\le sum\le 80$ | 无|$20 \operatorname{pts}$ | | $3$ | 无特殊限制 | 无特殊限制 |A| $15\operatorname{pts}$ | | $4$ | 无特殊限制 | 无特殊限制 |B| $20 \operatorname{pts}$ | | $5$ | $1\le T\le 1000$ | 无特殊限制 |C| $20 \operatorname{pts}$ | | $6$ | 无特殊限制 | 无特殊限制 |无| $15 \operatorname{pts}$ | 特殊性质 A：$a_{i,j}$ 在 $[0,10^9]$ 中均匀随机生成。 特殊性质 B：所有 $a_{i,j}>0$。 特殊性质 C：所有 $a_{i,j}\le 100$。