题目内容

江上两座水寨要按旧例比旗。我方与对方各备 $m$ 艘快艇。寨中留下一张对阵册：我方第 $i$ 艘对上对方第 $j$ 艘时，若册上为 1 则我方得 1 分，若为 -1 则我方得 -1 分。比旗共 $m$ 轮，每轮对方先从自己尚未出列的艇里派出一艘；我方看清来艇后，再从自己尚未出列的艇里派一艘应战。两艘艇对阵一次后都不再上场。

对方希望我方总分尽量低，我方希望总分尽量高，双方都按最优策略行动。胜负可以互相克制、甚至成环，并不存在绝对最强的一艘艇。请对每一场比旗，求出我方最终能拿到的总分。

约束：

• 1 $\le$ $q$ $\le$ $10$
• 1 $\le$ $m$ $\le$ $10^2$
• 对阵册每个数只可能是 1 或 -1

输入描述

第一行一个整数 $q$（1 $\le$ $q$ $\le$ $10$），表示比旗场数。

随后是 $q$ 场，每场格式如下：

• 第一行一个整数 $m$（1 $\le$ $m$ $\le$ $10^2$），表示每方快艇数量
• 接下来 $m$ 行，每行 $m$ 个整数 $g_{i,0},g_{i,1},\ldots,g_{i,m-1}$（每个为 1 或 -1），表示我方第 $i$ 艘对对方各艘的结果

输出描述

输出 $q$ 行，每行一个整数，表示该场在双方最优策略下我方的总分。

样例1

输入

2
1
-1
2
1 -1
1 1

输出

-1
2

说明

• 第一场只有一艘艇，册上是 -1，我方只能得 -1 分。
• 第二场我方两艘都能在合适搭配下取胜，最大匹配为 2，总分 $2\times 2 - 2 = 2。

样例2

输入

1
3
1 1 -1
1 -1 -1
-1 -1 1

输出

3

说明

三对都能配成我方获胜：例如 $(0,1)$、$(1,0)$、$(2,2)$。场数等于艇数，总分 $2\times 3 - 3 = 3。

样例3

输入

1
3
1 1 -1
-1 -1 -1
1 -1 -1

输出

1

说明

我方最多赢 2 场（第二艘对谁都输），总分 $2\times 2 - 3 = 1。