Under construction

Still being built. Things may change

Maximum Coins

Interview

Time limit20sMemory limit1024 MB

Summary
Each move goes diagonally down-right or up-left, so a path stays on one diagonal of the matrix; find the diagonal with the largest sum of coins.
Level

Easy3 of 10

Topics
Array, Prefix sum, Matrix, Implementation
Solved
No attempts yet

Problem

Mike has a square matrix with N rows and N columns. Cell (i,j) denotes the cell at row i and column j. Cell (1,1) denotes the top left corner of the matrix. Each cell has some number of coins associated with it, and Mike can collect them only if he visits that cell. Ci,j is the number of coins in the cell at row i and column j. From a cell (i,j), Mike can move to cell (i+1,j+1) or cell (i-1,j-1), as long as the target cell lies within the boundaries of the matrix and has not been visited yet. He can start the journey from any cell and stop at any point. Mike wants to maximize the number of coins he can collect. Determine the maximum number of coins he can collect.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The next N lines contain N integers each. The j-th integer in the i-th line is the number of coins Ci,j in cell (i,j).

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of coins Mike can collect.

Constraints

  • 1 ≤ T ≤ 100.
  • 0 ≤ Ci,j ≤ 107.

Hint

In Sample Case #1, the maximum number of coins collected can be 14 if Mike follows this path: (1,1) -> (2,2) -> (3,3).

In Sample Case #2, the maximum number of coins collected can be 9 if Mike follows this path: (2,3) -> (3,4).

Examples1

  1. Example 1

    Input
    2
3
1 2 5
3 6 1
12 2 7
5
0 0 0 0 0
1 1 1 1 0
2 2 2 8 0
1 1 1 0 0
0 0 0 0 0
    Expected output
    Case #1: 14
Case #2: 9