순환하는 삼각형

크기가 $N$인 직각삼각형 격자를 숫자로 채운다. 두 직각변의 길이는 모두 $N$이고, 한 변은 위쪽에 가로로, 다른 한 변은 오른쪽에 세로로 놓는다. 열은 왼쪽 끝이 $0$번, 오른쪽 끝이 $N-1$번이고, 행은 위쪽 끝이 $0$번, 아래쪽 끝이 $N-1$번이다. 따라서 직각은 $0$행 $N-1$열에 있고, $R$행 $C$열 칸은 $R \le C$일 때만 존재한다. 빗변은 $0$행 $0$열에서 $N-1$행 $N-1$열까지 이어진다.

채우기는 삼각형의 테두리를 한 바퀴 도는 방식으로 진행한다.

1. 직각의 반대쪽 끝인 $0$행 $0$열에서 시작해 가로변을 따라 오른쪽으로 $0$행 $N-1$열까지 채운다.
2. 이어서 세로변을 따라 아래로 $N-1$행 $N-1$열까지 채운다.
3. 다시 빗변을 따라 왼쪽 위로 올라가면서 $1$행 $1$열까지 채운다.

여기까지 채우고 나면 아직 비어 있는 칸은 $1$행 $2$열을 왼쪽 위 꼭짓점으로 하는 크기 $N-3$의 직각삼각형이 된다. 그 삼각형에 같은 규칙을 다시 적용하고, 크기가 $0$ 이하가 되면 멈춘다.

칸에 적는 숫자는 채운 순서를 따라 $1, 2, \dots, 9, 0, 1, 2, \dots$ 로 반복한다. 즉 $k$번째로 채운 칸에는 $k$를 $10$으로 나눈 나머지를 적는다.

$N = 10$이면 완성된 표는 다음과 같다. 점은 삼각형 바깥을 뜻한다.

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

$N$을 알면 어떤 칸의 숫자든 바로 구할 수 있다. 위 표에서 $0$행 $7$열은 $8$이고, $5$행 $7$열은 $2$다. 행 번호와 열 번호가 주어질 때 그 칸에 적힌 숫자를 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스의 첫 줄에는 삼각형의 크기 $N$과 질의의 개수 $Q$가 공백 하나를 사이에 두고 주어진다. ($1 \le N \le 1000000$, $1 \le Q \le 10$)

이어지는 $Q$개의 줄에는 각각 행 번호 $R$과 열 번호 $C$가 공백 하나를 사이에 두고 주어진다. ($0 \le R \le C < N$) 행과 열은 모두 $0$부터 센다.

질의마다 $R$행 $C$열 칸에 적힌 숫자를 한 줄에 하나씩, 입력에 주어진 순서대로 출력한다.