#216774. [GKS 2020 #G] Maximum Coins

Mike has a square matrix with rows and columns. Cell denotes the cell present at row and column . Cell denotes the top left corner of the matrix. Each cell has some amount of coins associated with it and Mike can collect them only if he visits that cell. represents the number of coins in cell with row and column . From a cell , Mike can decide to go to cell or cell , as long as the cell lies within the boundaries of the matrix and has not been visited yet. He can choose to start the journey from any cell and choose to stop at any point. Mike wants to maximize the number of coins he can collect. Please help him determine the maximum number of coins he can collect.

The first line of the input gives the number of test cases, . test cases follow. Each test case begins with a line containing the integer . The next lines contain integers each. The -th integer in the -th line represents the number of coins in cell .

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

样例输入 1

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

样例输出 1

Case #1: 14
Case #2: 9

In Sample Case #, the maximum number of coins collected can be , if Mike follows this path:

In Sample Case #, the maximum number of coins collected can be , if Mike follows this path:

.

Limits

.

.

Test Set

.

Test Set

in at most cases.

in all other cases.