Descr iption

2008六月激动人心的欧洲杯就要开始了，来直世界各地的人们都会涌向主办国瑞士和奥地利。由于比赛是在不同的城市进行，为了使球迷们能够尽快的到达各个城市，主办方决定在城市之间修建铁路来满足需要，铁路线当然越短越好喽。现在你的任务是帮助主办方选择最优的修建方案。



Input

输入的第一行是一个数n(2 <= n <= 50 )，表示城市的数目。

后面是一个n * n的矩阵A，A[i][j]表示第i个城市和第j个城市的路径(0 <= A[i][j] <= 100000)，城市编号从0到n-1

输入的第三行是一个数q，表示主办方有q次询问。

后面是q行，每行两个数 s，t (0 <= s ,t <= n-1),表示主办方需要询问从s到t的最短修建距离。





Output

输出有q行，每行一个数，s到t的最短修建距离-Descr iption

Exciting European Cup in June 2008 to begin to direct people around the world will flock to the host country, Switzerland and Austria. As competition in different cities, in order for fans to arrive as soon as possible in various cities, the organizers decided to build the railway between the cities to meet the needs of the railway line, of course the shorter the better myself. Now your task is to help the organizers choose the best rehabilitation program.



Input

Enter the first line is a number n (2 <= n <= 50), indicated that the number of cities.

Followed by an n* n matrix A, A [i] [j] represents the first i and j cities, cities in the path (0 <= A [i] [j] <= 100000), Urban numbered from 0 to n-1

The third line is an input number q, said the tournament has q queries.

Followed by the q lines of two numbers s, t (0 <= s, t <= n-1), said the organizers need to ask from s to t, the shortest distance from the construction.





Output

Output