using namespace std;

int main()
{
int matrix2[2][2] = {
1,2,
4,3 };

int matrix3[3][3] = {
1,2,3,
8,9,4,
7,6,5
};
int matrix4[4][4] = {
1, 2, 3, 4,
12,13,16,5,
11,14,15,6,
10, 9, 8,7
};
int matrix5[5][5] = {
1, 2, 3, 4, 5,
16,17,24,23,6,
15,18,25,22,7,
14,19,20,21,8,
13,12,11,10,9

};

int matrix6[6][6] = {
1, 2, 3, 4, 5, 6,
20,21,32,31,30,7,
19,22,33,34,29,8,
18,23,36,35,28,9,
17,24,25,26,27,10,
16,15,14,13,12,11
};

int matrix7[7][7] = {
1, 2, 3, 4, 5, 6, 7,
24,25,40,39,38,37,8,
23,26,41,42,43,36,9,
22,27,48,49,44,35,10,
21,28,47,46,45,34,11,
20,29,30,31,32,33,12,
19,18,17,16,15,14,13
};

int matrix8[8][8] = {
1, 2, 3, 4, 5, 6, 7, 8,
28,29,48,47,46,45,44,9,
27,30,49,50,51,52,43,10,
26,31,60,61,64,53,42,11,
25,32,59,62,63,54,41,12,
24,33,58,57,56,55,40,13,
23,34,35,36,37,38,39,14,
22,21,20,19,18,17,16,15
};

int matrix9[9][9] = {
1, 2, 3, 4, 5, 6, 7, 8, 9,
32,33,56,55,54,53,52,51,10,
31,34,57,58,59,60,61,50,11,
30,35,72,73,80,79,62,49,12,
29,36,71,74,81,78,63,48,13,
28,37,70,75,76,77,64,47,14,
27,38,69,68,67,66,65,46,15,
26,39,40,41,42,43,44,45,16,
25,24,23,22,21,20,19,18,17
};

int matrix10[10][10] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
36,37,64,63,62,61,60,59,58,11,
35,38,65,66,67,68,69,70,57,12,
34,39,84,85,96,95,94,71,56,13,
33,40,83,86,97,98,93,72,55,14,
32,41,82,87,100,99,92,73,54,15,
31,42,81,88,89,90,91,74,53,16,
30,43,80,79,78,77,76,75,52,17,
29,44,45,46,47,48,49,50,51,18,
28,27,26,25,24,23,22,21,20,19
};

int C;
cin >> C;
for (int c = 0; c < C; ++c)
{
int N, M;
cin >> N >> M;
for (int m = 0; m < M; ++m)
{
int x, y;
cin >> x >> y;
if (N == 1)
cout << 1 << endl;
else if (N == 2)
cout << matrix2[x][y] << endl;
else if (N == 3)
cout << matrix3[x][y] << endl;
else if (N == 4)
cout << matrix4[x][y] << endl;
else if (N == 5)
cout << matrix5[x][y] << endl;
else if (N == 6)
cout << matrix6[x][y] << endl;
else if (N == 7)
cout << matrix7[x][y] << endl;
else if (N == 8)
cout << matrix8[x][y] << endl;
else if (N == 9)
cout << matrix9[x][y] << endl;
else if (N == 10)
cout << matrix10[x][y] << endl;
}
}

return 0;
}