Ada the Ladybug is a well know farmer. As she has experience with building fences and breeding animals, she was asked by leader of local zoo - Lichsteiner Leech - to help them design a paddock for animals.

The problem is following: The zoo breeds very rare beasts called Tyg3Rs. There are few of them in a N x N square paddock with squares have different heights. The Tyg3Rs live in (little) squares and the breeders want them to play with each other. At first it is not possible to travel between distinct squares, but it is possible to connect any two adjacent squares for cost of absolute difference of their heights (by making slope).

Now, for each subset of Tyg3Rs, the zoo wants to know minimal price to connect the squares in such way, that each Tyg3R can get to each other. As the output would be pretty big, they just want you to sum these costs.

As her good friend (and as the instances are too big for her to handle), she has asked you to help her with this problem.

Input

The first line contains T, the number of test-cases.

The first line of each test-case contains 2 ≤ N ≤ 17, the size of big square.

Each of the next N lines contain N integers, the heights of each square. Each number is between 0 and 1000.

The next line contains 1 ≤ Q ≤ 10, the number of Tyg3Rs.

The next Q lines contains two integers: 0 ≤ x, y < N, the coordinates of Tyg3Rs. Note that multiple Tyg3Rs might already live in the same square.

Output

For each test-case print the sum of costs of cheapest way to connect all subset of Tyg3Rs.

Example Input

4
3
1 2 1
2 1 2
1 2 1
3
0 0
0 2
2 1
3
5 5 5
7 5 5
3 4 4
4
0 0
0 0
0 0
2 0
3
1 2 3
4 5 6
7 8 9
2
0 0
2 2
8
1 8 5 2 3 6 7 4
1 5 7 5 4 6 8 7
9 8 7 4 5 2 3 6
1 4 5 7 2 5 3 6
5 2 1 2 4 5 8 5
9 9 9 9 6 6 4 5
2 2 3 4 9 1 9 1
1 4 1 4 7 5 2 1
5
0 0
5 6
3 3
2 1
7 7

Example Output

12
14
8
441

Input Explanation

Prices of subsets of first test-case

000: 0
100: 0
010: 0
001: 0
110: 2
101: 3
011: 3
111: 4

For the second test-case, each subset costs 0, unless those, which consists of last Tyg3R (and some other) - those cost 2.

The third test-case has only one valuable subset (of both Tyg3Rs), which goes on top/right border, and costs 8.