Description

最短路径的算法在数据结构中学过,现在要求给定一定的点，求出两点间的最短路径.

Input

输入包含多组，每组首先包含一个n（n<=100），代表这组数据有n个点，然后是一个n*n的矩阵代表两两间的距离（s到t的距离可能不同于t到s的距离），一个点到自身的距离是0，任何一个数的不大于1000且是非负整数。数字地址从1到n标记。
输完后有不定数目组s,t代表起始点地址和终点地址，以0 0 结束
n=0时代表结束，这组数据不需要任何输出。

Output

每对s,t对应一个整数输出，表示s到t的最短距离。
每组数据后加一个空行分隔。

Sample Input

5
0 3 6 8 9
5 0 6 9 4 
1 3 0 84 1
45 1 2 0 4
1 4 5 8 0
1 2
1 3
1 4
5 4
4 3
4 1
3 4
0 0
2
0 1 
1 0
1 2
1 1
0 0
0

Sample Output

3
6
8
8
2
3
9

1
0

HINT

可能会出现一组数据里s,t很多甚至重复的情况，应将最短路径保存起来以供读取

Source

软件协会