P9153 「SvR-2」1+2=3（加强版）

你有一些木棒，每个木棒左边有一个数，右边有一个数，数是 $[0,c)$ 的自然数，你要将所有木棒拼起来，使相邻的数和为 $c$ 的对数最大。 例如，$c=3$，$1\text{ - }2$ 和 $1\text{ - }0$ 两个木棒，如果按 $1\text{ - }0,1\text{ - }2$ 这样拼，相邻的数和为 $3$ 的对数是 $0$；而按 $1\text{ - }\textcolor{red}{\underline{\textbf 2}},\textcolor{red}{\underline{\textbf 1}}\text{ - }0$ 这样拼相邻的数和为 $3$ 的对数是 $1$，因为 $2+1=3$。

**本题有多组数据。** 输入的第一行一个正整数表示数据组数 $T$。 对于每组数据，第一行输入一个正整数 $c$，之后 $c$ 行，每行 $c$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 为 $(i-1)\text{ - }(j-1)$ 型木棒的个数。

共 $T$ 行，每行一个整数表示答案。

对于 $100\%$ 的数据，$1\le T\le10^5$，$1\le a_{i,j}\le10^9$，$3\le c\le10^3$，$\sum c^2\le5\times10^6$。 **注：本题数据较弱，如有 hack 欢迎告知出题人。**