import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author: zhangyc
 * @date: 2020/9/27
 */
public class Main_netease_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int C = sc.nextInt();
        for (int i = 0; i < C; i++) {
            List<Integer> ret = new ArrayList<>();
            int N = sc.nextInt();
            int[][] maze = buildMaze(N);
            int M = sc.nextInt();
            for (int j = 0; j < M; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                ret.add(maze[x][y]);
            }
            for (Integer res : ret) {
                System.out.println(res);
            }
        }

    }

    public static int[][] buildMaze(int N) {
        int[][] storage = new int[N][N];
        int direction = 0;
        int number = 1;
        int curX = 0, curY = -1;
        while (number <= N * N) {
            switch (direction) {
                case 0:
                    curY++;
                    while (curY < N && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curY++;
                        number++;
                    }
                    curY--;
                    direction = 1;
                    break;
                case 1:
                    curX++;
                    while (curX < N && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curX++;
                        number++;
                    }
                    curX--;
                    direction = 2;
                    break;
                case 2:
                    curY--;
                    while (curY >= 0 && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curY--;
                        number++;
                    }
                    curY++;
                    direction = 3;
                    break;
                case 3:
                    curX--;
                    while (curX >= 0 && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curX--;
                        number++;
                    }
                    curX++;
                    direction = 4;
                    break;
                case 4:
                    curX++;
                    while (curX < N && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curX++;
                        number++;
                    }
                    curX--;
                    direction = 5;
                    break;
                case 5:
                    curY++;
                    while (curY < N && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curY++;
                        number++;
                    }
                    curY--;
                    direction = 6;
                    break;
                case 6:
                    curX--;
                    while (curX >= 0 && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curX--;
                        number++;
                    }
                    curX++;
                    direction = 7;
                    break;
                case 7:
                    curY--;
                    while (curY >= 0 && storage[curX][curY] == 0) {
                        storage[curX][curY] = number;
                        curY--;
                        number++;
                    }
                    curY++;
                    direction = 0;
                    break;
                default:
                                        break;
            }    
        }
        return storage;
    }
}