Dengue is all across the nation and blood donation is an immediate need now-a-days. Dr. Bari runs a blood donation group called Orbachin. His group operates as follows:
- Someone in need of blood makes a request for blood collection from city v.
- Orbachin posts this request to it's subscribers.
- Someone else who can fulfill the request, residing at city u, donates the blood.
Moving from city u to v may take a lot of time, depending on traffic jam, rainfall and other conditions. In order to make things faster, Dr. Bari has estimated the time of moving between each pair of cities of this country. He has published a chart in his group, showing his estimated time for traveling between different pairs of cities. He has requested his volunteers to follow this chart. But the problem is, there are plenty of cities in this country and the volunteers may get confused by looking at this chart. So, Bari has made a better plan.
Whenever, a volunteer agrees to donate blood from city u to city v, he will take at most one intermediate city to reach from u to v. That means, if the direct path from u to v is more time consuming, then a person can first go to an intermediate city x and then move to city v.
Now given the chart and the volunteers response, suggest Dr. Bari a shortest path of length at most 2 from city u to city v.
Input
The first line contains a number N ( 1 ≤ N ≤ 100 ), the number of cities in the country.
The next N lines each contain N integers, the j'th integer of the i'th line indicates the cost of moving from city i to city j. The time cost will be non-negative and will be at most 1000. Please also note that the i'th number of the i'th line will always be 0, as there is no cost from moving within the same city.
The next line contains a number Q ( 1 ≤ Q ≤ 10000 ), the number of operations that Orbachin needs to handle.
The next Q lines will contain two integers u and v ( 0 ≤ u,v < N ), indicating that blood needs to be donated from city u to city v.
Output
For each query, please print one line, the minimum time it takes to move from city u to city v using at most one intermediate city.
Sample
| Input | Output |
|---|---|
2 0 500 500 0 2 0 1 1 0 | 500 500 |
