PLAYMAT - Play with Matrices

no tags 

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?

[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

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



Added by:Sharaf
Date:2013-02-07
Time limit:0.109s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:2013 acmASCIS Level 1 Contest