题目描述

你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 $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}$ 之和。

特殊性质 A：$a_{i,j}$ 在 $[0,10^9]$ 中均匀随机生成。

特殊性质 B：所有 $a_{i,j}>0$。

特殊性质 C：所有 $a_{i,j}\le 100$。