Problem Description

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

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, 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 Format

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

1
3
4 1 3
4 7 7
9 10 3

31

Hint

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