#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
#include <cassert>

using namespace std;
typedef pair<int, int> PII;

const int INF = 0x3FFFFFFF;

int a[810][810];

	PII T[4000000];

	inline void update(PII &a, const PII &b){
		a = PII(min(a.first, b.first), max(a.second, b.second));
	}
	
	void build(int k, int x0, int x1, int y0, int y1){
		if (x0 == x1 && y0 == y1) {
			T[k] = PII(a[x0][y0], a[x0][y0]);
			return;
		}
		int m1 = (x0 + x1) >> 1;
		int m2 = (y0 + y1) >> 1;
		int kk = k << 2;
		build(kk + 1, x0, m1, y0, m2);
		T[k] = T[kk + 1];

		if (m1 < x1) {
			build(kk + 2, m1 + 1, x1, y0, m2);
			update(T[k], T[kk + 2]);
		}
		if (m2 < y1) {
			build(kk + 3, x0, m1, m2 + 1, y1);
			update(T[k], T[kk + 3]);
		}
		if (m1 < x1 && m2 < y1) {
			build(kk + 4, m1 + 1, x1, m2 + 1, y1);
			update(T[k], T[kk + 4]);
		}
	}
	
	void add(int k, int X0, int X1, int Y0, int Y1, int x, int y, int val) {
		if (X0 == X1 && Y0 == Y1) {
			T[k] = PII(val, val);
			return;
		}
		int m1 = (X0 + X1) >> 1;
		int m2 = (Y0 + Y1) >> 1;
		int kk = k << 2;
		if (x <= m1 && y <= m2){
			add(kk + 1, X0, m1, Y0, m2, 		x, y, val);
		}
		if (m1 < X1 && y <= m2 && x > m1) {
			add(kk + 2, m1 + 1, X1, Y0, m2, 	x, y, val);
		}
		if (x <= m1 && m2 < Y1 && y > m2) {
			add(kk + 3, X0, m1, m2 + 1, Y1, 	x, y, val);
		}
		if (m1 < X1 && m2 < Y1 && x > m1 && y > m2) {
			add(kk + 4, m1 + 1, X1, m2 + 1, Y1, x, y, val);
		}
		T[k] = T[kk + 1];
		if (m1 < X1) update(T[k], T[kk + 2]);
		if (m2 < Y1) update(T[k], T[kk + 3]);
		if (m1 < X1 && m2 < Y1) update(T[k], T[kk + 4]);
	}
	PII get(int k, int X0, int X1, int Y0, int Y1, int x0, int x1, int y0, int y1) {
		if (x0 == X0 && x1 == X1 && y0 == Y0 && y1 == Y1) {
			return T[k];
		}
		int m1 = (X0 + X1) >> 1;
		int m2 = (Y0 + Y1) >> 1;
		int kk = k << 2;
		PII res(INF, -INF);
		if (x0 <= m1 && y0 <= m2)
			update(res, get(kk + 1, X0, 	m1, Y0, 	m2, 	x0, min(x1, m1), y0, min(y1, m2)));

		if (m1 < X1 && y0 <= m2 && m1 < x1) 
			update(res, get(kk + 2, m1 + 1, X1, Y0, 	m2, 	max(x0, m1 + 1), x1, y0, min(y1, m2)));

		if (x0 <= m1 && m2 < Y1 && m2 < y1)
			update(res, get(kk + 3, X0, 	m1, m2 + 1, Y1,		x0, min(x1, m1), max(y0, m2 + 1), y1));

		if (m1 < X1 && m2 < Y1 && m1 < x1 && m2 < y1) 
			update(res, get(kk + 4, m1 + 1, X1, m2 + 1, Y1, 	max(x0, m1 + 1), x1, max(y0, m2 + 1), y1));
		return res;
	}


int main()
{
	int T_T, n, m, cas = 0;
	scanf("%d", &T_T);
	while (T_T--) {
		printf("Case #%d:\n", ++cas);
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				scanf("%d", &a[i][j]);
			}
		}
		build(0, 1, n, 1, n);
		for (int i = 0; i <= 10; i++) {
			//cout << T[i].first << ' ' << T[i].second << endl;
		}
		scanf("%d", &m);
		while (m--) {
			int x, y, L;
			scanf("%d%d%d", &x, &y, &L);
			int x0 = max(1, x - L / 2);
			int x1 = min(n, x + L / 2);
			int y0 = max(1, y - L / 2);
			int y1 = min(n, y + L / 2);
			PII res = get(0, 1, n, 1, n, x0, x1, y0, y1);
			int ans = (res.first + res.second) >> 1;
			printf("%d\n", ans);
			add(0, 1, n, 1, n, x, y, ans);
		}
	}
	return 0;
}