The delivery company Scrooge Co. wants to establish a system to pay its employees the minimum money in their travels. The company has information about which the minimum cost to go from a location to another one is.

They ask you for getting a solution to compute the minimum amount of money that an employee will receive to go from one location to another one and which the route that he should use to arrive in is.

The Input

The input begins with a single  integer 1<= C <= 99 on a line by itself, indicating the number of test cases following, each of them as described below.

For each test case, the first line has an integer 1<= P <=  99, indicating the number of  locations we consider for this case. The second line gives us the name of each location separated by a TAB, each name has at most 20 characters.The next P lines contain the minimum cost to go from one location to another one separated by a TAB, the first line have the costs between the first location and the rest, the second line are the costs between the second location and the rest, and so on. A cost is an integer -1<= C<= 300, where -1 means that is too expensive a travel between the locations, and 0 is used to indicate the cost from a location to the same location.

After the P lines there is an integer 1<= R <=  99, indicating the number of routes that we have to consider. Following R lines containing the name of the employee, the start location and the end location. The locations names are case sensitive and the name of the employee has at most 30 characters.

The Output

For each test case you should produce one or two outputs line.

If a route between the locations exists, you will produce two lines, one with the cost and other with the path according to this format

"Mr <employee name> to go from <orig name> to <dest name>, you will receive <minimum cost> euros"
"Path:<orig name> <locations separated by a blank> <dest name>"

If a route between the locations does not exist, you will produce one line, according to this format:

"Sorry Mr <employee name> you can not go from <orig name> to <loc name>"

Sample Input

2
6
Ofi1	Ofi2	Ofi3	ofi4	ofi5	ofi6
0	4	1	-1	4	-1
4	0	-1	2	3	4
1	-1	0	-1	3	-1
-1	2	-1	0	-1	1
4	3	3	-1	0	2
-1	4	-1	1	2	0
1
Pepito	Ofi1	ofi4
3
Murcia	Alicante	Albacete
0	3	-1
-1	0	4
-1	-1	0
2
Dofyl	Murcia	Albacete
Dofyl	Albacete	Murcia

Sample Output

Mr Pepito to go from Ofi1 to ofi4, you will receive 6 euros
Path:Ofi1 Ofi2 ofi4
Mr Dofyl to go from Murcia to Albacete, you will receive 7 euros
Path:Murcia Alicante Albacete
Sorry Mr Dofyl you can not go from Albacete to Murcia

OMP'06
Facultad de Informatica
Universidad de Murcia (SPAIN)