#include "testlib.h"
#include <unordered_set>

using namespace std;
// B L K F R T

// L R U D
vector<vector<int>> const ROTATE_CUBE = {
	{4, 0, 2, 3, 5, 1},
	{3, 1, 0, 5, 4, 2},
};

vector<int> const DR = {0, 1};
vector<int> const DC = {1, 0};
string const DIRS = "RD";
int const ALL_COLORS = 1 << 24;

vector<int> rotate(vector<int> const &cube, int dir) {
	vector<int> res(6);
	for (int i = 0; i < 6; i++) {
		res[i] = cube[ROTATE_CUBE[dir][i]];
	}
	return res;
}

struct state {
	vector<int> cube;
	int row;
	int column;

	bool operator==(state const &other) const {
		return row == other.row && column == other.column && cube == other.cube;
	}
};

template<>
struct std::hash<state> {
	static const unsigned int P = 239017;

    std::size_t operator()(state const& s) const {
    	unsigned int hash = 0;
    	for (int i = 0; i < 6; i++) {
    		hash = hash * P + s.cube[i];
    	}
    	hash = hash * P + s.row;
    	hash = hash * P + s.column;
    	return hash;
    }
};

bool path_exists(state start, vector<vector<int>> const &field) {
	unordered_set<state> used;
	vector<state> queue;
	used.insert(start);
	queue.push_back(std::move(start));
	int size = (int) field.size();
	while (!queue.empty()) {
		state cur = std::move(queue.back());
		queue.pop_back();
		for (int dir = 0; dir < 2; dir++) {
			int nRow = cur.row + DR[dir];
			int nCol = cur.column + DC[dir];
			if (nRow >= size || nCol >= size) {
				continue;
			}
			state nState { rotate(cur.cube, dir), nRow, nCol };
			if (field[nRow][nCol] != nState.cube[0]) {
				continue;
			}
			if (nRow + 1 == size && nCol + 1 == size) {
				return true;
			}
			if (used.insert(nState).second) {
				queue.push_back(std::move(nState));
			}
		}
	}
	return false;
}

bool readAns(InStream &ouf, vector<vector<int>> const &field, string const &prefix_msg) {
	string const answer = ouf.readToken("Yes|No", "answer");
	if (answer == "No") {
		return false;
	}
	vector<int> cube(6);
	for (int i = 0; i < 6; i++) {
		cube[i] = ouf.readInt(0, ALL_COLORS - 1, format("a[%d]", i));
	}
	state init { cube, 0, 0 };
	if (field[0][0] != cube[0]) {
		ouf.quitf(_wa, "%s: bad initial color %d != %d", prefix_msg.c_str(), field[0][0], cube[0]);
	}
	if (!path_exists(std::move(init), field)) {
		ouf.quitf(_wa, "%s: no path exists", prefix_msg.c_str());
	}
	return true;
}

bool checkTest(string const &prefix_msg) {
	int size = inf.readInt();
	vector<vector<int>> field(size, vector<int>(size));
	for (auto &row : field) {
		for (auto &cell : row) {
			cell = inf.readInt();
		}
	}
	string const msg = format("%s: n = %d", prefix_msg.c_str(), size);
	bool pa = readAns(ouf, field, msg);
	bool ja = readAns(ans, field, msg);
	if (pa && !ja) {
		quitf(_fail, "%s: participant found correct solution, this was unexpected", msg.c_str());
	}
	if (!pa && ja) {
		quitf(_wa, "%s: solution exists, but was not found", msg.c_str());
	}
	return ja;
}

int main(int argc, char **argv) {
	registerTestlibCmd(argc, argv);
	int testsCount = inf.readInt();
	int yesCount = 0;
	for (int test = 0; test < testsCount; test++) {
	    setTestCase(test + 1);
		string msg = format("Case %d of %d", test + 1, testsCount);
		yesCount += checkTest(msg) ? 1 : 0;
	}
	quitf(_ok, "%d cases, %d of them 'Yes'", testsCount, yesCount);
}
