Untitled

package day19_2306;

import java.util.Scanner;

public class hugo_mat_ong {
	
	static int row, col;
	static long ans;
	static int[][] map;
	static int[][] dl = {{-1, 0, 1, 1, 1, 0}, {0, 1, 1, 0, -1, -1}};
	static int[][] dc = {{-1, -1, 0, 1, 0, -1}, {0, 1, 1, 0, -1, -1}};
	static boolean[][] visit;
	
	private static void DFS(int x, int y, int sum, int cnt){
//		visit[x][y] = true;
		if(cnt == 4){
			ans = sum > ans ? sum : ans;
			return;
		}
			
		int dx, dy;
		for(int i = 0; i < 6; i++){
			if(y % 2 == 0){
				dx = x + dc[0][i]; dy = y + dc[1][i];
			}
			else{
				dx = x + dl[0][i]; dy = y + dl[1][i];
			}
			
			if(dx >= 0 && dy >= 0 && dx < row && dy < col && !visit[dx][dy]){
				visit[dx][dy] = true;
				DFS(dx, dy, sum + map[dx][dy], cnt + 1);
				visit[dx][dy] = false;
			}
		}
	}
	
	public static void DFS2(int x, int y){
		int suml = map[x][y], sumc = map[x][y], cntl = 1, cntc = 1;
		int dx, dy;
		for(int i = 0; i < 6; i++){
			if(i % 2 == 0){
				dx = x + dc[0][i]; dy = y + dc[1][i];
				if(dx >= 0 && dy >= 0 && dx < row && dy < col){
					cntc++;
					sumc += map[dx][dy];
				}
			}
			else{
				dx = x + dl[0][i]; dy = y + dl[1][i];
				if(dx >= 0 && dy >= 0 && dx < row && dy < col){
					cntl++;
					suml += map[dx][dy];
				}
			}
		}
		
		if(cntc == 4) ans = sumc > ans ? sumc : ans;
		if(cntl == 4) ans = suml > ans ? suml : ans;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			col = sc.nextInt(); row = sc.nextInt();

			
			map = new int[row][col];
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					map[i][j] = sc.nextInt();
				}
			}

			visit = new boolean[row][col];
			ans = 0;
			for(int i = 0; i < row; i++){
				for(int j = 0; j < col; j++){
					visit[i][j] = true;
					DFS(i, j, map[i][j], 1);
					visit[i][j] = false;
					DFS2(i, j);
				}
			}
			
			ans = ans * ans;
			System.out.println("Case #" + tc);
			System.out.println(ans);
		}
	}

}