题目描述

披萨店$Pizazz Pizzeria$以其快速配送披萨为傲。不幸的是，由于预算削减，他们只能雇佣一名司机进行配送。该司机会等待1到10个订单处理完成后才开始配送。显然，他希望选择最短路径配送所有订单并返回披萨店，即使需要重复经过某些地点或多次路过披萨店。他请你编写一个程序帮助他计算最优路径。

输入格式

输入包含多个测试用例。
每个测试用例的第一行为一个整数$n$，表示需要配送的订单数（$1 \leq n \leq 10$）。
接下来的$n + 1$行，每行包含$n + 1$个整数，表示从披萨店（编号为$0$）到$n$个配送点（编号$1$至$n$）之间的直接通行时间。
第$i$行的第$j$个值表示从地点$i$直接到地点$j$的时间（不经过其他地点）。
注意：由于交通状况不同，$i \rightarrow j$和$j \rightarrow i$的时间可能不同。
可能存在更快的间接路径（通过其他地点中转）。
输入以$n = 0$结束。

输出格式

对每个测试用例，输出一个整数，表示完成所有配送并返回披萨店的最短总时间。

示例

输入数据 1

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

输出数据 1

8

来源

East Central North America $2006$