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

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 connection costs, C_i,j is the cost of edge (i, j), if there is no edge between i, j then C_{i, j} = -1 else 1 ≤ C_i,j ≤ 10000.
            C_1,2    C_1,3    ... C_1,N
            C_2,3    C_2,4    ... C_2,N
            ...
            C_N-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, destination ≤ N.

Output

For each test case, output a single line of output in the form "Case K: A₁ A₂ ... A_q" where K is the number of the test case and [A₁ A₂ ... A_q] are the answers for the Q queries. 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 there is no path between 2 cities, the answer is -1.

Example

Input:
1
4
2 -1 3
1 7
10
2
2 1
3
0 3 4
1 3 4
2 3 4

Output:
Case 1: 10 8 6