Woburn Challenge 2001

Having been briefed by John Patrick Mason that his mission was a failure, M decides on another course of action. Instead of influencing who will be the winner, she will simply find out who it is ahead of time (remember, the series is aired several months after it is shot). She will send her best agent, James Bond, to infiltrate CBS headquarters and determine who will be the winner.

Having found an answer, Bond temporarily eludes CBS security (see the declassified documents in problem 9 for how he does it). He now finds himself next to the CBS logo (a big golden eye) on the ground floor of headquarters with the required information. A chopper will meet him there and pick him up shortly. However, CBS security, along with their Apache attack helicopter, has been mobilized and begins to chase Bond into the street. Commandeering a car, Bond drives through the city to avoid the attack helicopter trying to blow him away. However, the attack helicopter cannot seem to hit Bond and keeps taking out the road right behind his car, thus preventing him from traveling the same road (or intersection) again. As Bond drives through the city, he realizes that he has to meet the chopper as soon as possible back at the CBS building where he started. However, since the roads behind him are being taken out, he can never take the same road or the same intersection twice. Fortunately, the OnStar navigation system in his car was programmed by P (Q's boss, Peter Plachta) and tells him the quickest route to take to get back to the CBS building and the total distance he would be traveling on this cyclic route. Note that it just happens to turn out that the distance the computer quotes is the shortest such route in the entire city.

Your job is the following. Given a roadmap of the city in the form of an adjacency matrix ~A~ (where ~A_{ij}~ – the distance between intersections ~i~ and ~j~ – is a positive integer), find out the distance that the computer quotes. Remember some of the rules:

• All roads are two-way. The CBS building is on one of the intersections.
• Neither the same intersection, nor the same road can be traveled twice (except for the starting intersection, which is the CBS building).
• Bond has to start and end in the same place (CBS).
• The cyclic route that Bond takes from CBS just happens to be the shortest cycle in the city.

Input Specification

The first line contains ~T~, the number of test cases.
The first line of each test case contains ~N~, the number of intersections in the city ~(1 \le N \le 100)~. The next ~N~ lines contain an adjacency matrix giving the distances between intersections in the city; a distance of -1 is given for ~A_{ij}~ then there is no direct connection from intersection ~i~ to intersection ~j~ or if ~i=j~. Each distance is a positive integer ~\le 300~.

Output Specification

For each test case, output a line with the minimum distance Bond must travel to loop back to the CBS building. If there is no such cyclic route that will allow Bond to return to CBS headquarters, print out Infinity.

Sample Input

2
3
-1 1 1
1 -1 2
1 2 -1
5
-1 6 5 3 -1
6 -1 -1 -1 -1
5 -1 -1 -1 -1
3 -1 -1 -1 2
-1 -1 -1 2 -1

Sample Output

4
Infinity