题目描述

一位旅行者计划在n个城市旅游，但是每个城市来回的价格是不同的。

旅行者现在位于城市1，他想要提前规划好路线，在保证每一个城市只前往1次，并在最后回到城市1的情况下，花费最少的金钱来完成这次旅游。


因此他希望你能帮他求出完成这次旅行所需的最小代价。

输入格式

第1行输入一个正整数 T (1

每1组测试样例第 1 行输入一个正整数 n (2 

接下来 n 行，每一行 n 个整数 pij (0 (当且仅当 i == j 时，pij = 0)

输出格式

输出 T 行，每一行为完成此次旅行所需的最少金钱数量。

1
4
0 3 6 7
5 0 2 3
6 4 0 2
3 7 5 0

10

提示

在上述测试样例中，旅行者的计划路线是 1 → 2 → 3 → 4 → 1。

因此完成旅行需要的代价为 p12 + p23 + p34 + p41 = 3 + 2 + 2 + 3 = 10。