Floyd Warshall Travel Queries

This problem requires you to compute the shortest travel times between pairs of cities using the Floyd-Warshall algorithm. You are given multiple datasets. For each dataset, a square matrix is provided which denotes the travel time between cities. A value of \(-1\) in the matrix indicates that there is no direct route between the cities.

For each query, you are asked to determine the shortest travel time between the two given cities. If no route exists between the cities, output \(-1\). The recurrence relation used in the algorithm is given by:

$$ d_{ij} = \min\{ d_{ij},\; d_{ik}+d_{kj} \} $$

where \(d_{ij}\) is the current shortest distance from city \(i\) to \(j\), and the indices \(i,j,k\) range over the set of cities.

inputFormat

The first line contains an integer \(T\) representing the number of datasets.

For each dataset:

• The first line contains an integer \(n\) representing the number of cities.
• The next \(n\) lines each contain \(n\) space-separated integers, representing the travel times between cities. A \(-1\) indicates that there is no direct connection.
• The following line contains an integer \(q\) representing the number of queries.
• Each of the next \(q\) lines contains two space-separated integers \(u\) and \(v\), representing a query to find the shortest travel time from city \(u\) to city \(v\) (0-indexed).

outputFormat

For each query, output the shortest travel time on a new line. If no path exists between the queried cities, output \(-1\).

## sample

1
3
0 3 -1
3 0 5
-1 5 0
2
0 2
2 0

8
8

</p>