建树（~2MB）

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for (; !isdigit(c); c = getchar())
		if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	return x * f;
}

#define r(a) (a) = read()

int kase;
int dim;
short t[1 << 20];
bool img[512][512];
string ans;

int chk(int x, int y, int dim) {
	int sta = -1;
	for (int i = x; i < x + dim; i++)
		for (int j = y; j < y + dim; j++) {
			if (img[i][j] == 1 && sta == 0)
				return -1;
			if (img[i][j] == 0 && sta == 1)
				return -1;
			sta = img[i][j];
		}
	return sta;
}

void build(int x, int y, int dim, int p) {
	int sta = chk(x, y, dim);
	//printf("DEBUG %d %d %d %d %d\n", x, y, dim, p, sta);
	if (sta >= 0) {
		t[p] = sta;
		return;
	}
	t[p] = 2;
	dim >>= 1;
	build(x, y, dim, (p << 2));
	build(x, y + dim, dim, (p << 2) + 1);
	build(x + dim, y, dim, (p << 2) + 2);
	build(x + dim, y + dim, dim, (p << 2) + 3);
}

void bfs() {
	queue<int> q;
	q.push(1);
	while (q.size()) {
		short now = q.front(); q.pop();
		if (t[now] == 2) {
			ans += "1";
			q.push((now << 2)    );
			q.push((now << 2) + 1);
			q.push((now << 2) + 2);
			q.push((now << 2) + 3);
		}
		else if (t[now] == 0) ans += "00";
		else if (t[now] == 1) ans += "01";
	}
}

string str2hex(string& str) {
	string ans = "";
	int len = str.length();
	int rem = len % 4;
	if (rem) {
		for (int i = 0; i < 4 - rem; i++)
			str = "0" + str;
	}
	for (int i = 0; i < len; i += 4) {
		int num = 0;
		for (int j = 0; j < 4; j++) {
			num <<= 1;
			num += str[i + j] - '0';
		}
		if (num < 10)
			ans += '0' + num;
		else
			ans += 'A' + num - 10;
	}
	return ans;
}

signed main() {
	r(kase);
	while (kase--) {
		r(dim);
		memset(t, 0x3f, sizeof t);
		ans = "";
		for (int i = 0; i < dim; i++)
			for (int j = 0; j < dim; j++)
				r(img[i][j]);
		build(0, 0, dim, 1);
		bfs();
		//cout << ans << "\n";
		cout << str2hex(ans) << "\n";
	}
	
	return 0;
}

不建树（~500KB）

inline int read() {
	char c = getchar();
	int x = 0, f = 1;
	for (; !isdigit(c); c = getchar())
		if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - 48;
	return x * f;
}

#define r(a) (a) = read()

int kase;
int dim;
bool img[512][512];
string ans;

struct node {
	int x, y, dim;
};

int chk(int x, int y, int dim) {
	int sta = 2;
	for (int i = x; i < x + dim; i++)
		for (int j = y; j < y + dim; j++) {
			if (img[i][j] == 1 && sta == 0)
				return 2;
			if (img[i][j] == 0 && sta == 1)
				return 2;
			sta = img[i][j];
		}
	return sta;
}

void bfs() {
	queue<node> q;
	q.push({0, 0, dim});
	while (q.size()) {
		auto now = q.front(); q.pop();
		int x = now.x, y = now.y, dim = now.dim;
		int sta = chk(x, y, dim);
		if (sta == 2) {
			ans += "1";
			dim >>= 1;
			q.push({x, y, dim});
			q.push({x, y + dim, dim});
			q.push({x + dim, y, dim});
			q.push({x + dim, y + dim, dim});
		}
		else if (sta == 0) ans += "00";
		else if (sta == 1) ans += "01";
	}
}

string str2hex(string& str) {
	string ans = "";
	int len = str.length();
	int rem = len % 4;
	if (rem) {
		for (int i = 0; i < 4 - rem; i++)
			str = "0" + str;
	}
	for (int i = 0; i < len; i += 4) {
		int num = 0;
		for (int j = 0; j < 4; j++) {
			num <<= 1;
			num += str[i + j] - '0';
		}
		if (num < 10)
			ans += '0' + num;
		else
			ans += 'A' + num - 10;
	}
	return ans;
}

signed main() {
	r(kase);
	while (kase--) {
		r(dim);
		ans = "";
		for (int i = 0; i < dim; i++)
			for (int j = 0; j < dim; j++)
				r(img[i][j]);
		bfs();
		//cout << ans << "\n";
		cout << str2hex(ans) << "\n";
	}
	
	return 0;
}