有n个城市，编号为1~n，有些城市之间有路相连，有些没有。Lh在城市1，要去跟在城市n的女朋友约会，Lh想尽快见到女朋友，所以不想走太多的路，但是Lh有一个习惯就是只从编号小的城市到编号大的城市，问Lh要走的路最短距离是多少。

注意：
    若Lh一开始就和其女朋友在一个城市，那么Lh显然就不需要再长途跋涉的对吧。

输入的第一行包含一个正整数T（T<=20），表示一共有T组数据.

每组数据先输入一个n，表示城市个数，1<=n<=100;

接着有n行，没行有n个数。第一行表示第一个城市跟n个城市之间的道路情况。

map[i,j]=0，表示城市i，j之间没有路，否则就是i，j之间道路的距离。0<=map[i][j]<=100;数据保证有答案。

一个正整数表示Lh从1到n要走的最短的距离。答案占一行。