Cyclic Triangle

A right triangle grid of size $N$ is filled with digits. Both legs have length $N$. One leg lies horizontally along the top, the other lies vertically along the right side. Columns are numbered $0$ at the left end through $N-1$ at the right end, and rows are numbered $0$ at the top through $N-1$ at the bottom. The right angle is therefore at row $0$, column $N-1$, and the cell at row $R$, column $C$ exists only when $R \le C$. The hypotenuse runs from row $0$, column $0$ to row $N-1$, column $N-1$.

The filling walks once around the border of the triangle.

1. Start at row $0$, column $0$, the end of the horizontal leg opposite the right angle, and fill rightward along that leg up to row $0$, column $N-1$.
2. Continue downward along the vertical leg to row $N-1$, column $N-1$.
3. Then move up and to the left along the hypotenuse, filling as far as row $1$, column $1$.

The cells that are still empty now form a right triangle of size $N-3$ whose top left corner is row $1$, column $2$. Apply the same rule to that triangle, and stop once the size drops to $0$ or below.

The digits follow the filling order and repeat as $1, 2, \dots, 9, 0, 1, 2, \dots$. The $k$-th cell filled gets the remainder of $k$ divided by $10$.

For $N = 10$ the finished table is shown below. A dot marks a position outside the triangle.

1234567890
.789012341
..65678952
...5445063
....433174
.....32285
......2196
.......107
........08
.........9

Once $N$ is known, the digit in any cell can be found directly. In the table above, row $0$, column $7$ holds $8$, and row $5$, column $7$ holds $2$. Given a row index and a column index, report the digit written in that cell.

The first line contains the number of test cases $T$ ($1 \le T \le 10$).

The first line of each test case contains the triangle size $N$ and the number of queries $Q$, separated by a single space ($1 \le N \le 1000000$, $1 \le Q \le 10$).

Each of the next $Q$ lines contains a row index $R$ and a column index $C$, separated by a single space ($0 \le R \le C < N$). Rows and columns are both counted from $0$.

For each query print the digit written in the cell at row $R$, column $C$, one per line, in the order the queries are given.