说明

有一块多边形的披萨饼，上面有很多蔬菜和肉片，我们希望沿着两个不相邻的顶点切成小三角形，并且尽可能少地切碎披萨上面的蔬菜和肉片。 可以把披萨看作一个凸多边形，任何两个顶点的连线对应的权值代表上面的蔬菜和肉片数，我们希望沿着两个不相邻的顶点切成小三角形，尽可能少地切碎披萨上面的蔬菜和肉片。那么，该问题可以归结为凸多边形的最优三角剖分问题。

假设把披萨看作一个凸多边形，标注各顶点为${v_0，v_1，…，v_n}$。那么怎么得到它的最优三角剖分呢？

输入格式

第一行是一个整型数$m(m<100)$表示共有$m$组测试数据。

每组测试数据的第一行是一个整数$n(0<n<1000)$表示顶点的个数。

接下来为$n$行，$n$列，共$n×n$个整数$g_{ij}((0<g_{ij}<1000))$，表示顶点$ij$之间的权值。

输出格式

对于每一组输入，输出最优三角剖分权值之和。

每组的输出占一行。

样例

2
6
0 2 3 1 5 6
2 0 3 4 8 6
3 3 0 10 13 7
1 4 10 0 12 5
5 8 13 12 0 3
6 6 7 5 3 0
4
0 5 12 7
8 0 9 20
25 12 0 18
30 26 15 0

54
63

来源

《趣学算法》4.7节