P9153 "SvR-2" 1+2=3 (Enhanced Version).

You have some wooden sticks. Each stick has a number on the left and a number on the right. The numbers are natural numbers in $[0,c)$. You need to connect all sticks together so that the number of adjacent pairs whose sum is $c$ is as large as possible. For example, when $c=3$, 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, the first line contains a positive integer $c$. Then follow $c$ lines, each containing $c$ integers. The $j$-th integer in the $i$-th line, $a_{i,j}$, is the number of sticks of type $(i-1)\text{ - }(j-1)$.

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

For $100\%$ of the testdata, $1\le T\le10^5$, $1\le a_{i,j}\le10^9$, $3\le c\le10^3$, $\sum c^2\le5\times10^6$. **Note: The testdata for this problem is relatively weak. If you have any hacks, please let the problem setter know.** Translated by ChatGPT 5