Spiral Chess

All submissions for this problem are available.

The legend says that chess was invented in India; the inventor of the game, Sassi, requested from the Brahman Rai Bhalit a modest payment: 1 grain of wheat for the first square, 2 for the second, 4 for the third, 8 for the fourth, and so on up to the sixty fourth square of the board. The Brahman, being so naive accepted the request and asked his court to make the payment to Sassi. Soon he realized that there was not enough wheat in all India to pay Sassi. Because of that, Rai Bhalit ordered another payment to Sassi based on the game he invented.

The Brahman proposed the following game to Sassi: "I will give you a sequence of numbers and you have to place them in the chess board in an spiral way. Then, I will give you several rectangles Q_i inside the board, and for each one of them you have to give me the minimum between the sum of the numbers placed on the black squares in Q_i and the sum of the numbers placed on the white squares in Q_i. If you are able to do so, I will give you the sum of the numbers in the whole board in gold coins. If you are not, your head will roll."

Being really slow to sum many numbers, Sassi requested his son Shah to help him due his outstanding ability to write programs in Whitespace. Nevertheless, Shah was not able to find a good Whitespace compiler in Rai Bhalit's palace so he is asking you to solve this problem with a more sophisticated language.

The following figure shows the way a 4x4 board is filled with the sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16.

Note that every chess board starts with a white square in the top-left corner and the sequence could be composed by any numbers.

Input

The first line contains an integer T, which specifies the number of test cases. Then, T test case descriptions will follow.

Each test case will start with a line with one positive integer N, indicating the size of the chess board. The next line will contain N² numbers to fill the chess board in the way described before.

The following line will have a positive integer Q, which specified the number of queries for this test case. Then Q query descriptions will follow.

Each query is described by a line with four integers R₁, C₁, R₂ and C₂, indicating the corners of a rectangle to be processed, where the pairs (R₁,C₁) and (R₂,C₂) indicate the tiles at the top-left corner and the bottom-right corner of the rectangle, respectively.

Output

For each input case you must print the string "Case #i:" in a line, where i is the test case number, starting from 1. Then, for each query made for that test case, you must print the result of it in its own line. You must print a new line after every test case.

Example

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

Output
Case #1:
0
0
3
4

Case #2:
10
10
20

Constraints

T will be between 1 and 200, inclusive.
N will be between 2 and 100, inclusive.
Each element inside the sequence will be between 1 and 104, inclusive.
Q will be between 1 and 10000, inclusive.
R1, C1, R2, C2 will be between 0 and N-1, inclusive, for all queries.
R1 will be lower than or equal to R2 for each query.
C1 will be lower than or equal to C2 for each query.