#include <bits/stdc++.h>

using namespace std;

int buildMap(vector<vector<int>> &mp, int lx, int ly, int rx, int ry, bool flag, int start) {
	//flag==true:顺时针
	//flag==false:逆时针
	//返回下一圈的起始值
	if (flag == true) {
		for (int i = ly; i <= ry; ++i)
			mp[lx][i] = start++;
		for (int i = lx + 1; i <= rx; ++i)
			mp[i][ry] = start++;
		int h = rx - lx;
		if (h > 0) {
			for (int i = ry - 1; i >= ly; --i)
				mp[rx][i] = start++;
		}
		int w = ry - ly;
		if (w > 0) {
			for (int i = rx - 1; i > lx; --i)
				mp[i][ly] = start++;
		}
	}
	else {
		for (int i = lx; i <= rx; ++i)
			mp[i][ly] = start++;
		for (int i = ly + 1; i <= ry; ++i)
			mp[rx][i] = start++;
		int w = ry - ly;
		if (w > 0) {
			for (int i = rx - 1; i >= lx; --i)
				mp[i][ry] = start++;
		}
		int h = rx - lx;
		if (h > 0) {
			for (int i = ry - 1; i > ly; --i)
				mp[lx][i] = start++;
		}
	}
	return start;
}

int main() {
	int C = 0;
	cin >> C;
	while (C--) {
		int N, M;
		cin >> N >> M;
		vector<vector<int>> mp(N, vector<int>(N, 0));
		int lx = 0, ly = 0;
		int rx = N - 1, ry = N - 1;
		int start = 1;
		bool flag = true;
		while (lx <= rx && ly <= ry) {
			start = buildMap(mp, lx++, ly++, rx--, ry--, flag, start);
			if (flag == true)
				flag = false;
			else
				flag = true;
		}

		/*
		for (int i = 0; i < mp.size(); ++i) {
			for (int j = 0; j < mp[0].size(); ++j) {
				cout << mp[i][j] << " ";
			}
			cout << endl;
		}*/
		
		vector<int> ans;
		while (M--) {
			int x, y;
			cin >> x >> y;
			ans.emplace_back(mp[x][y]);
		}

		for (auto &v : ans)
			cout << v << "\n";
	}
	system("pause");
}

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>

using namespace std;

int caluDescriptor(unordered_map<int, string> &mp) {          //计算最小描述符
	int descriptor = 0;
	while (true) {
		if (mp.find(descriptor) == mp.end())
			return descriptor;
		++descriptor;
	}
}

void Process(vector < pair<string, vector<string>>> &Instr, vector<string> &ans) {
	unordered_map<int, string> mp;        //描述符，文件名
	set<int> Dsecs;     //备选描述符集

	for (int i = 0; i < Instr.size(); ++i) {
		Dsecs.insert(i);
	}

	for (auto &p : Instr) {
		string Ins = p.first;      //指令
		vector<string> Parameter = p.second;     //参数
		int descriptor = 0;
		if (Ins == "open") {
			//descriptor = caluDescriptor(mp);        //删除备选描述符，查找最小描述符
			descriptor = *(Dsecs.begin()); Dsecs.erase(Dsecs.begin());
			mp[descriptor] = Parameter[0];
			ans.emplace_back(to_string(descriptor));
		}
		else if (Ins == "dup") {
			//descriptor = caluDescriptor(mp);              //删除备选描述符，查找最小描述符
			descriptor = *(Dsecs.begin()); Dsecs.erase(Dsecs.begin());
			mp[descriptor] = mp[atoi(Parameter[0].c_str())];
			ans.emplace_back(to_string(descriptor));
		}
		else if (Ins == "close") {
			mp.erase(atoi(Parameter[0].c_str()));           //插入备选描述符
			Dsecs.insert(atoi(Parameter[0].c_str()));
		}
		else if (Ins == "query") {
			ans.emplace_back(mp[atoi(Parameter[0].c_str())]);
		}
		else if (Ins == "dup2") {
			int descriptor1 = atoi(Parameter[1].c_str());
			int descriptor2 = atoi(Parameter[0].c_str());
			mp[descriptor1] = mp[descriptor2];
			auto iter = Dsecs.find(descriptor1);
			if (iter != Dsecs.end())
				Dsecs.erase(iter);
		}
	}
}

int main() {
	int T = 0;
	cin >> T;
	while (T--) {
		int N = 0;
		vector<pair<string, vector<string>>> Instr;       //指令，参数
		cin >> N;
		vector<string> ans;         //答案
		while (N--) {
			string Ins = "";
			cin >> Ins;
			if (Ins == "dup2") {
				string s1, s2;
				cin >> s1 >> s2;
				vector<string> tmp;
				tmp.emplace_back(s1);
				tmp.emplace_back(s2);
				Instr.emplace_back(make_pair(Ins, tmp));
			}
			else {
				string s1;
				cin >> s1;
				vector<string> tmp;
				tmp.emplace_back(s1);
				Instr.emplace_back(make_pair(Ins, tmp));
			}
		}

		Process(Instr, ans);

		for (auto &s : ans)
			cout << s << "\n";
	}
	return 0;
}