P9088 "SvR-2" 1+2=3

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

**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 $T$ lines. Each line contains one integer, the answer.

#### 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. | Subtask | $T$ | $sum$ | Special Property | Score | | :------: | :------: | :------: | :------: | :------: | | $1$ | $1 \leq T \leq 10$ | $1\le sum\le 10$ | None | $10 \operatorname{pts}$ | | $2$ | $1 \leq T \leq 50$ | $1\le sum\le 80$ | None | $20 \operatorname{pts}$ | | $3$ | No special limits | No special limits | A | $15\operatorname{pts}$ | | $4$ | No special limits | No special limits | B | $20 \operatorname{pts}$ | | $5$ | $1\le T\le 1000$ | No special limits | C | $20 \operatorname{pts}$ | | $6$ | No special limits | No special limits | None | $15 \operatorname{pts}$ | 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