최대 동전 수

Mike에게 N개의 행과 N개의 열로 이루어진 정사각 행렬이 있다. 셀 (i,j)는 i행 j열에 있는 셀을 나타낸다. 셀 (1,1)은 행렬의 왼쪽 위 모서리를 나타낸다. 각 셀에는 일정한 수의 동전이 있으며, Mike는 해당 셀을 방문해야만 그 동전을 수집할 수 있다. $C_{i,j}$는 i행 j열에 있는 셀의 동전 수를 나타낸다. 셀 (i,j)에서 Mike는 셀 (i+1,j+1) 또는 셀 (i-1,j-1)로 이동할 수 있다. 단, 해당 셀이 행렬의 경계 안에 있고 아직 방문하지 않은 셀이어야 한다. 그는 어느 셀에서든 여정을 시작할 수 있고, 어느 시점에서든 멈출 수 있다. Mike는 수집할 수 있는 동전의 수를 최대화하려 한다. 그가 수집할 수 있는 동전의 최대 개수를 구하라.

제한

시간 제한: 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 0 ≤ $C_{i,j}$ ≤ $10^{7}$.

테스트 세트 1

1 ≤ N ≤ 100.

테스트 세트 2

최대 10개의 경우에 1 ≤ N ≤ $10^{3}$. 그 외의 모든 경우에 1 ≤ N ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N이 포함된 한 줄로 시작한다. 다음 N개의 줄에는 각각 N개의 정수가 주어진다. i번째 줄의 j번째 정수는 셀 (i,j)에 있는 동전의 수 $C_{i,j}$를 나타낸다.

각 테스트 케이스마다 Case #x: y이 포함된 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 Mike가 수집할 수 있는 동전의 최대 개수이다.

예제 케이스 #1에서 Mike가 다음 경로를 따르면 수집하는 동전의 최대 개수는 14이 될 수 있다: (1,1) -> (2,2) -> (3,3)

예제 케이스 #2에서 Mike가 다음 경로를 따르면 수집하는 동전의 최대 개수는 9이 될 수 있다: (2,3) -> (3,4).