Matrices are fun, You’re given a squared matrix and you should travel on the matrix frame and its diagonal (As in Figure). Dividing the frame sum by its diagonal sum, as we go deeper in frames we sum up all these frames divided by their diagonals. So can you sum all valid divisons?

Example:

( (1+2+3+4+8+12+16+15+14+13+9+5)/(1+6+11+16) ) + ( (6+7+11+10)/(6+11) ) = 3 + 2 = 5

Note: Use integer division(Example: 3/2 = 1).

Input

First line of input contains number of test cases T where (0 <= T <= 300). Followed by the size of the squared matrix N where (1<N<30) followed by N^2 positive integers representing the Matrix.

Note: summations may overflow.

Output

For each test case output "Case_#i:_X" where "X" is the result and "i" is the number of the test case (starting with 1) and "_" is white space, Each output should be in a separate line.

Example

Input:
1
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Output:
Case #1: 5