题目描述

作为编程小镇中最资深的程序员，小李对编程充满热情，这天他突发奇想，决定将素数与编程完美结合，创造出一个前所未有的作品——素数方阵。这个方阵是将前 $N^2$ 个素数从右下角按照图示规律依次填入 $N \times N$ 的方阵就得到了素数方阵。以下是 $N=4$ 和 $N=5$ 的素数方阵：

参赛者需要编写一个程序，找出 $N \times N$ 素数方阵中某些方格中的素数。现在给你一些数据，请你判断在该素数方阵中对应方格中的素数是多少。

输入格式

第一行两个正整数 $N$ 和 $M$，$N$ 表示 $N \times N$ 的素数方阵，$M$ 表示有 $M$ 个方格。

接下来的 $M$ 行，每行有两个正整数 $x$ 和 $y$，分别表示该方格在素数方阵中的第 $x$ 行第 $y$ 列，每行相邻的两个数之间均用一个空格隔开。

输出格式

$M$ 行，每行一个整数，分别对应询问的素数。

样例

4 2
3 3
1 2

41
13

数据范围

• 对于 $100\%$ 的数据，$1\le x,y\le N\le 100$，$1\le M\le 100$。