Problem Description

You have some wooden sticks. Each stick has a number on the left and a number on the right. The numbers can only be $0,1,2$. You need to connect all sticks together, and make the number of adjacent pairs whose sum is $3$ as large as possible.

For example, there are two sticks $1\text{ - }2$ and $1\text{ - }0$. If you connect them as $1\text{ - }0,1\text{ - }2$, then the number of adjacent pairs whose sum is $3$ is $0$. But if you connect them as $1\text{ - }\textcolor{red}{\underline{\textbf 2}},\textcolor{red}{\underline{\textbf 1}}\text{ - }0$, then the number of adjacent pairs whose sum is $3$ is $1$, because $2+1=3$.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case, one line contains $9$ non-negative integers, representing the counts of sticks of type $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$, respectively.

Output Format

Output $T$ lines. Each line contains one integer, the answer.

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

Hint

Constraints

For all testdata, $1\le T\le 10^5$. Let $a_{i,j}$ be the number of sticks of type $i\text-j$. It is guaranteed that $0\le a_{i,j}\le 10^9$.

This problem enables bundled tests and O2 optimization by default.

Let $sum$ be the sum of all $a_{i,j}$ over all test cases in one test point.

Special Property A: $a_{i,j}$ are generated uniformly at random in $[0,10^9]$.

Special Property B: All $a_{i,j}>0$.

Special Property C: All $a_{i,j}\le 100$.

Translated by ChatGPT 5