题目描述

你有一些木棒，每个木棒左边有一个数，右边有一个数，数是 $[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$ 行，每行一个整数表示答案。

1
3
4 1 3
4 7 7
9 10 3

31

提示

对于 $100\%$ 的数据，$1\le T\le10^5$，$0\le a_{i,j}\le10^9$，$3\le c\le10^3$，$\sum c^2\le5\times10^6$。

注：本题数据较弱，如有 hack 欢迎告知出题人。