Description

披萨店以尽可能快地向顾客提供披萨而自豪。司机将等待一个或多个（最多$10$个）订单被处理，然后开始送货。他愿意走最短的路线运送这些货物，然后返回比萨店，即使这意味着途中要经过相同的地点或披萨店不止一次。

Format

Input

输入包含多个测试用例。每个测试用例的第1行都包含一个整数$n（1≤n≤10）$，表示要交付的订单数量。之后$n+1$行中的每一行都包含$n+1$个整数，表示披萨店（编号$0$）和$n$个位置（编号为$1～n$）之间的行程时间。第i行上的第j个值表示从位置i直接到位置$j$的时间，时间值可能不对称，即从位置i直接到位置$j$的时间可能与从位置j直接到位置i的时间不同。$n=0$时将终止输入。

Output

对每个测试用例，都单行输出交付所有披萨并返回披萨店的最短时间。

Samples

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

8