Kingdom CODE is the most peaceful place in the universe. King NOVOSH and Queen ALMIDA is ruling this country peacefully. There are M houses in the kingdom. They are numbered from 0 to M-1.
But a sudden earthquake has just divided the planet into multiple parts. Let's call the part island. The houses are distributed in various islands and the king and queen got separated. In this valentine day king NOVOSH wants to meet with queen ALMIDA. You have to determine the minimum time the king NOVOSH have to travel to meet ALMIDA provided that the king can move 1 unit distance per minute.
The system of moving from one place to another is now a bit complicated. If you want to move to some house in the same island you can do so by using the roads. From each house there is road to every other house. But for moving from an island to another island you have to use a magical road. This magical road appears out of nowhere and can take you to any other house on a different island. But the distance of the road may vary depending on from which city you want to start and which city you want to go.
Input
Input starts with an integer T (T<=10), denoting the number of test cases.
Each case begins with an integer N (1 <= N <= 50). The next part contains the data of N islands. Each island is numbered from 1 to N. Each part starts with an integer S (1 <= S <= 50), the number of houses in this island. The next line contains S space separated integers denoting the id of the houses in this island. The next S lines each contain S integer. The integer at ith line jth column denotes the distance of the road between the ith house and the jth house in the list of the houses of this island. The distance could be at most 10000.
The next n lines contain n integers each. The j th integer at the i th line contains an integer which is the distance of the magical road between island numbered i to island numbered j. This distance will also be at most 10000.
Next line will contain an integer q (0 < q < 100001), denotes number of query. Each of next q line contains two integer u, v where u, v represent the house of king and the queen.
Output
For each case print the case number as “Case #%d:” in the first line. And for each query qi the minimum time to travel from house u to house v in a separate line.
Sample
| Input | Output |
|---|---|
1 2 2 0 3 0 5 5 0 2 1 2 0 2 2 0 0 3 3 0 4 0 3 1 2 0 1 2 3 | Case #1: 5 2 3 3 |
All M houses are present in the kingdom and each house is present in exactly 1 island.
This problem was authored for Inter Department Programming Contest 2016 at Jahangirnagar University and is being hosted on Toph per author's request.
