In a country of N cities, the government would like to develop a new system that can answer drivers’ queries to find the shortest path between 2 cities in the country road network. However, some cities are more exciting than others, and drivers would prefer driving through them. Last month, a voting for the most exciting cities in the country was conducted, and a ranking of the P most exciting cities has been made. The government decided to utilize this ranking so that drivers can find the shortest path between 2 cities that only goes through the first K cities of the ranking as intermediate cites on the road. Hence, the query is defined as: the source city, the destination city, and K for the first K cities from the ranking. (Note that some cities may not be exciting at all, and so they will not be included in the ranking, i.e. P <= N)

Given undirected graph representing the country cities, and ranked list of exciting cities, you are to answer Q quires, each one asking for the shortest path between 2 cities utilizing only the first K cities from the ranked list.

For example, given the graph in the sample (4 cities and ranked list [2 1])

1- Query(k=0, Src=3, dest=4): means no cities to use as intermediate, hence only direct path allowed à 3-4 with cost 10 2- Query(k=1, Src=3, dest=4): means we can use first city on list (2), hence we can choose between paths (3-4, 3-2-4) à path 3-2-4 with cost 8 is best 3- Query(k=2, Src=3, dest=4): means we can use first 2 cities on list (1, 2), hence we can choose between paths (3-4, 3-2-4, 3-2-1-4) à path 3-2-1-4 with cost 6 is best

 

Input Specification:

The first line of input contains an integer T that represents the number of test cases, then follow T test cases, each in following format:

Line 1

            N (1 ≤ N ≤ 150), the number of cities of the country

N-1 lines follow, where ith line represents ith- city connections' costs, Ci,j is the cost of edge (i, j), if there is no edge between i, j then Ci, j = -1 else, 1 ≤ Ci,j ≤ 10000

            C1, 2    C1, 3    ... C1, N

            C2, 3    C2, 4    ... C2, N

            ...

            CN-1, N

Line N+1

            P (0 ≤ P ≤ N), represents the size of ranked list

Line N+2

            P space-separated list of distinct cities ids (1 <= city id <= N)

Line N+3

            Q (1 ≤ Q ≤ 6000), represents the number of queries

Q lines follow

            K source destination

....

 

Note that: 0 ≤ K ≤ P, 1≤ source ≤ N and 1≤ destination ≤ N

 

Output Specification:

For each test case, output a single line of output in the form “Case K: A1 A2 …Aq” where K is the number of the test case and [A1 A2 … Aq] are the answers for the Q quires. Each answer is the shortest path cost between the 2 given cities using the first only K cities of given list as intermediate cities. In case no path between 2 cities, the answer is -1

Sample input:

1

4

2 -1 3

1 7

10

2

2 1

3

0 3 4

1 3 4

2 3 4

Sample Output:

Case 1: 10 8 6