Kingdom of Rohan is under attack! There are N vital army stations. King will decide what army should be guarding what station, to get the best strategic advantage against Sauron attacks. All armies are already in some stations, but not necessarily the stations required by the king. As a result armies will have to be moved. Distances between any pair of stations are known. They are not necessarily symmetrical, because road from station A to B could be different than road from B to A. When a army moves, it doesn't have to take a direct road and instead can choose to cross other stations, if that results in a shorter path.

Given the distances between stations and king's relocation orders, find the minimum total travel distance for all the armies.

Input

First line contains an integer T, number of test cases. Then the description of T test cases follow. Each test case starts with an integer N, which is the total number of army stations. Next N lines have N integers each, description of distances. b'th integer on line a is the distance from station a to station b. Description of kings orders follows. In a first line, a single integer R, number of orders. Next R lines will contain two integers s and d each, describing an order to move an army from station s to d.

Constrains:

1 <= T <= 50

1 <= N, R <= 50

1 <= distance <= 10^6

1 <= s, d <= N

Output

Print a single line for each test case. A string "Case #t: " without quotes, where t is the number of test case, starting from 1. Following the string, you must print the total distance armies must travel during relocation.

0 <= total distance <= 10^7

Example

Input:
1
3
0 1 1
1 0 1
1 9 0
2
2 1
3 2

Output:
Case #1: 3