You are aboard the luxury liner Neptune, which is flooding fast. See if you can make it off the ship before drowning!
The schematics of the ship can be described by a series of locations (e.g., cabins, lounges, and various other rooms) and paths (e.g., hallways, elevators, Christmas trees, and stairs) between the locations (as well as the time it takes to travel along these paths). You must determine the shortest amount of time it takes to get from your starting location to the rescue team. Unfortunately, there are a series of explosions occurring on the ship that cause certain locations and the paths to and from those locations to flood, and if you are in these locations or paths when the explosions occur, you will drown. Also, you cannot travel through a location once it is flooded. Note that if you reach a non-flooded location at the same exact time as the path you were previously on is flooded, or if you reach the rescue team at the same exact time its location is flooded, you would not drown at that time (i.e. you "win" ties).
Input to this problem will begin with a line containing a single integer N (1 ≤ N ≤ 100) indicating the number of data sets. Each data set will consist of a series of lines:
For each data set in the input, print a single line with the shortest amount of time in minutes it takes to reach the location of the rescue team from your starting location without drowning (if possible). If it is not possible to reach the location of the rescue team, output "GENE HACKMAN".
2 3 1 3 1 0 1 2 2 5 0 1 4 0 0 0 3 1 3 0 0 1 0 2 0 0 2 0 0 0 0
2 GENE HACKMAN