Ghayboza loves puzzle games specially Rubik's cube but he is not patient enough to spend all that time solving it, he takes the concept “life is too short” very seriously, so he thought he could build a robot to help him solve this cube.

Ghayboza has numbered the cube for the robot to understand according to the color of the cell in such a way that the summation of the corners tells the robot its next move. Robot gets the numbers in the cube as slices starting from the nearest one.

A cube is made by grouping square slices together as shown in this figure.

Each letter represents a single slice of the cube. Ghayboza is asking you as an ACMer to write a program that operates the robot to decide its movements.

Input

Your program will be tested on one or more test cases. The first line of input will be a single integer T, representing the number of test cases (1 <= T <= 10). Each case starts with an integer N (1 < N <= 10) that indicates the length of the cube, followed by N×N lines representing the rows in each slice of the cube and an empty line between each two slices. Each line contains N integers indicating the value of each cell Vi (0 <= Vi < 2^63).

Output

For each test case, print “Case_#i:_X” where “X” is a single integer indicates the summation of the corners in the cube, “i” is the number of the test case (starting with 1) and “_” is a space. Each output should be printed in a separate line.

Example

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

10 11 12
13 14 15
16 17 18

19 20 21
22 23 24
25 26 27
2
20000 31000
34000 40000

21000 30000
90000 24000

Output:
Case #1: 112
Case #2: 290000