Problem: Irving & Cohen Petroleum Corporation has decided to develop a new oil field in an area. A preliminary survey has been done and they created a detailed grid map of the area which indicates the reserve of oil.

They are now planning to construct mining plants on several grid blocks according this map, but they decided not to place any two plants on adjacent positions to avoid spreading of fire in case of blaze. Two blocks are considered to be adjacent when they have a common edge. You are one of the programmers working for the company and your task is to write a program which calculates the maximum amount of oil they can mine, given the map of the reserve.



Input

The first line of the input specifies N, the number of test cases. Then N test cases follow, each of which looks like the following:


W H
r1,1 r2,1 . . . rW,1
...
r1,H r2,H . . . rW,H


The first line of a test case contains two integers W and H (1 ≤ W, H ≤ 20). They specifies the dimension of the area. The next H lines, each of which contains W integers, represent the map of the area. Each integer rx,y (0 ≤ rx,y < 10000) indicates the oil reserve at the grid block (x, y).

Output

For each test case, output the case number (starting from 1) and the maximum possible amount of mining in a line. Refer to the sample output section about the format.

Example

Input

2
2 2
2 3
3 5
3 2
4 1 1
2 1 4


Output

Case 1: 7
Case 2: 8

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

struct Dinic {
	using Flow = int;
	struct Edge {
		int to, rev;
		Flow cap;
		Edge() {}
		Edge(int to, int rev, Flow cap) :to(to), rev(rev), cap(cap) {}
	};
	int n;
	vector<vector<Edge>> g;
	vector<bool> used;
	vector<int> level;
	vector<int> iter;
	Dinic(int n) :n(n), g(n), used(n), level(n), iter(n) {};
	void addArc(int from, int to, Flow cap) {
		g[from].emplace_back(to, (int)g[to].size(), cap);
		g[to].emplace_back(from, (int)g[from].size() - 1, 0);
	}
	void addEdge(int a, int b, Flow cap) {
		g[a].emplace_back(b, (int)g[b].size(), cap);
		g[b].emplace_back(a, (int)g[a].size() - 1, cap);
	}
	Flow maximumFlow(int s, int t) {
		Flow total = 0;
		while (true) {
			levelize(s);
			if (level[t] < 0)return total;
			fill(iter.begin(), iter.end(), 0);
			Flow f;
			while (true) {
				f = augment(s, t, INF);
				if (f == 0)break;
				total += f;
			}
		}
	}
	Flow augment(int v, int t, Flow f) {
		if (v == t)return f;
		for (int &i = iter[v]; i < g[v].size(); i++) {
			Edge &e = g[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				Flow d = augment(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					g[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	void levelize(int s) {
		fill(level.begin(), level.end(), -1);
		queue<int> q;
		level[s] = 0;
		q.emplace(s);
		while (q.size()) {
			int v = q.front(); q.pop();
			for (int i = 0; i < g[v].size(); i++) {
				Edge &e = g[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.emplace(e.to);
				}
			}
		}
	}
};

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	rep(c, 1, N + 1) {
		int W, H; cin >> W >> H;
		vector<vector<int>> r(H, vector<int>(W));
		int sum = 0;
		rep(i, 0, H) rep(j, 0, W) { cin >> r[i][j]; sum += r[i][j]; }
		Dinic dinic(W*H + 2);
		int s = dinic.n - 2, t = s + 1;
		auto inrange = [&](int i, int j) { return i >= 0 && i < H && j >= 0 && j < W; };
		rep(i, 0, H) {
			rep(j, 0, W) {
				if ((i + j) % 2 == 0) {
					dinic.addArc(s, i*W + j, r[i][j]);
					static const int di[] = { 1,0,-1,0 };
					static const int dj[] = { 0,1,0,-1 };
					rep(k, 0, 4) {
						int ni = i + di[k], nj = j + dj[k];
						if (inrange(ni, nj)) {
							dinic.addArc(i*W + j, ni*W + nj, INF);
						}
					}
				}
				else {
					dinic.addArc(i*W + j, t, r[i][j]);
				}
			}
		}
		cout << "Case " << c << ": " << sum - dinic.maximumFlow(s, t) << endl;
	}
	return 0;
}