{"raw_statement":[{"iden":"statement","content":"你有一些木棒，每个木棒左边有一个数，右边有一个数，数是 $[0,c)$ 的自然数，你要将所有木棒拼起来，使相邻的数和为 $c$ 的对数最大。\n\n例如，$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$。"},{"iden":"input","content":"**本题有多组数据。**\n\n输入的第一行一个正整数表示数据组数 $T$。\n\n对于每组数据，第一行输入一个正整数 $c$，之后 $c$ 行，每行 $c$ 个整数，第 $i$ 行第 $j$ 个整数 $a_{i,j}$ 为 $(i-1)\\text{ - }(j-1)$ 型木棒的个数。"},{"iden":"output","content":"共 $T$ 行，每行一个整数表示答案。"},{"iden":"note","content":"对于 $100\\%$ 的数据，$1\\le T\\le10^5$，$1\\le a_{i,j}\\le10^9$，$3\\le c\\le10^3$，$\\sum c^2\\le5\\times10^6$。\n\n**注：本题数据较弱，如有 hack 欢迎告知出题人。**"}],"translated_statement":null,"sample_group":[["1\n3\n4 1 3\n4 7 7\n9 10 3\n","31\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}