背景

WZland的紧急避难所很快就建好了，WZland的居民们陆续地来到这个紧急避难所。但WZland的许多居民不肯躲避，他们想要和外星人正面作战……

问题描述

在紧急避难所内，应广大居民的要求，WZland的国王决定成立一个自卫队，自卫队由WZOI的JHB来担任领导。 JHB成为自卫队的领导之后，他的首要任务就是制作武器。WZland盛产矿石，每一种矿石中都含有巨大的能量。当两块矿石相结合，会有一块消失而另一块保留下来，并且会产生巨大能量。JHB想通过吸收这些能量，制造出一种能量化的武器，这个武器的杀伤力就是产生的能量总和。

JHB找人弄到了若干块不同的矿石（每种矿石有且只有一种），他想用这些矿石制作出杀伤力最大的武器。他把这些矿石交给WZOI的你，然后你需要制作出他需要的武器。当然一个武器是不够的，JHB陆续给你送来了若干组矿石，你需要将每组的矿石都制作成武器。

输入格式

输入数据第一行包含一个整数T，表示有T组矿石； 对于每组矿石会有若干行来描述。

第一行包含一个整数N，表示当前组矿石的种类。

接下来N行每行N个整数，第i行的第j个数表示矿石i和矿石j结合，然后j消失i留下产生的能量。

输出格式

输出数据有T行，每行一个整数S，分别表示矿石造出来的武器的最大杀伤力。

样例输入输出

Sample #1weapon.in

1
3
0 10 1
11 0 3
4 5 0

weapon.out

16

Sample #2weapon.in

2
2
0 4
1 0
3
0 20 1
12 0 1
1 10 0

weapon.out

4
22

样例解释

对于Sample #2 的第二个测试点，我们可以这样制作武器：1 和2 合并留下2，获得能量12，3 和2 合并留下3，获得能量10，总能量为22。

数据规模

对于30%的数据，2≤N≤10，T≤10；

对于50%的数据，2≤N≤10，T≤100；

对于100%的数据，2≤N≤10，T≤500；

对于100%的数据，保证S≤Maxlongint。