#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void init(vector<vector<int> >& matrix, int n) {
    int left = 0, right = n - 1, up = 0, down = n - 1;
    int tmp = 1;
    int flag = 0;
    while(1) {

        if (flag == 0) { // 顺时针建图
            for (int i = left; i <= right; i++) {
                matrix[up][i] = tmp++;
            }
            if (++up > down) {
                break;
            }
            for (int i = up; i <= down; i++) {
                matrix[i][right] = tmp++;
            }
            if (--right < left) {
                break;
            }
            for (int i = right; i >= left; i--) {
                matrix[down][i] = tmp++;
            }
            if (--down < up) {
                break;
            }
            for (int i = down; i >= up; i--) {
                matrix[i][left] = tmp++;
            }
            if (++left > right) {
                break;
            }
            flag = 1;
        } else { // 逆时针建图
            for (int i = up; i <= down; i++) {
                matrix[i][left] = tmp++;
            }
            if (++left > right) {
                break;
            }
            for (int i = left; i <= right; i++) {
                matrix[down][i] = tmp++;
            }
            if (--down < up) {
                break;
            }
            for (int i = down; i >= up; i--) {
                matrix[i][right] = tmp++;
            }
            if (--right < left) {
                break;
            }
            for (int i = right; i >= left; i--) {
                matrix[up][i] = tmp++;
            }
            if (++up > down) {
                break;
            }
            flag = 0;
        }
    }
}

int main() {
    int c;
    cin >> c;
    int m, n;
    int tx, ty;
    while(c--) {
        cin >> m >> n;
        vector<vector<int> > matrix(m, vector<int>(m, 0));
        init(matrix, m);
        for (int i = 0; i < n; i++) {
            cin >> tx >> ty;
            cout << matrix[tx][ty] << endl;
        }
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

void open_dup(string file, vector<string>& fes, priority_queue<int>& q, int& tmp) {
    // 获取最新的tmp值
    while(fes[tmp] != "*") {
        tmp++;
    }
    // 获取最新的队顶值，如果队内的文件描述符在dup2中被操作过，需要过滤
    while(!q.empty() && fes[q.top() * -1] != "*"){
        q.pop();
    }
    if (!q.empty() ) {
        fes[q.top() * -1] = file;
        cout << q.top() * -1 << endl;
        q.pop();
    } else {
        fes[tmp] = file;
        cout << tmp << endl;
        tmp++;
    }
}

int main() {
    int n;
    cin >> n;
    while(n--) {
        int m;
        cin >> m;
        int tmp = 0;
        priority_queue<int> q;
        vector<string> files(1000005, "*");
        string opt, file;
        int idx, idx2;
        while(m--) {
            cin >> opt;
            if (opt == "open") {
                cin >> file;
                open_dup(file, files, q, tmp);
            } else if (opt == "dup") {
                cin >> idx;
                file = files[idx];
                open_dup(file, files, q, tmp);
            } else if (opt == "dup2") {
                cin >> idx >> idx2;
                file = files[idx];
                files[idx2] = file;
            } else if (opt == "close") {
                cin >> idx;
                if (idx < tmp) {
                    q.push(idx * -1);
                }
                files[idx] = "*";
            } else if (opt == "query") {
                cin >> idx;
                cout << files[idx] << endl;
            }
        }
    }
    return 0;
}