说明

长江游艇俱乐部在长江上设置了n个游艇出租站，游客可以在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为$r_{(i,j)}$，1≤i<j≤n。试设计一个算法，计算从游艇出租站i到出租站j所需的最少租金。

输入格式

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

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

第2行共n(n-1)/2个整数，是站点i,j之间的租金$r_{(i,j)}$(0<i<=n,i<j<=n,0<$r_{(i,j)}$<1000)。

输出格式

对于每一组输入，输出第1个站点到第n个站点的最少租金。

每组的输出占一行。

样例

2
6
2 6 9 15 20 3 5 11 18 3 6 12 5 8 6
4
4 6 10 8 5 2

15
8

来源

《趣学算法》4.5节