Daniel is one of the most famous taxi drivers in the world. He always takes passengers to their location quickly. But today he has just picked up a strange passenger, Mr. CA. Mr. CA doesn’t care how much time Daniel uses to take him to his destination, but he wants Daniel’s car to maintain a constant speed, with the speed as high as possible. This confuses Daniel because he only remembers the shortest path, so Mr. CA became angry very quickly and got off the car.
Daniel is so sad and you must help him.
You are given some information about the roads that connect some cities together and their speed limit and some pairs of start cities and end cities. Help Daniel to find the maximum constant speed he could achieve.
There’s a number k in the first line, denoting the number of test cases, followed by k test
cases. Each test case start with a number n, 2<=n<=500, denoting the number of cities, followed by a n by n matrix, which are the speed limit between cities, 0<=speed limit<=100, speed limit equals to zero means there’s no road connect two cities. Following is a number q and q lines, each line contains two different number, the start city number and end city number, respectively. The city number start from 1 to n.
For each query, output the maximum constant speed Daniel could achieve in a line.
1 3 0 1 2 1 0 3 2 3 0 3 1 2 1 3 2 3
2 2 3
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|