该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

偏移素数查询

题目描述

给定一个固定的奇数 $D$。

若正整数 $x$ 同时满足以下条件，则称 $x$ 为一个合格数：

1. $x$ 是奇数；
2. $x$ 是素数；
3. $(x+D)/2$ 是素数。

你需要回答 $Q$ 次询问。每次询问给出一个闭区间 $[l,r]$，请输出该区间内合格数的个数。

输入格式

第一行输入两个整数 $D,Q$，其中 $1\le D\le 99999$，$D$ 为奇数，$1\le Q\le 100000$。

接下来 $Q$ 行，每行输入两个整数 $l,r$，表示一次询问，保证 $1\le l\le r\le 100000$。

由于只对奇数 $x$ 判断第三个条件，所有可能出现的 $(x+D)/2$ 都是不超过 $100000$ 的整数。

输出格式

输出 $Q$ 行。第 $i$ 行输出第 $i$ 次询问对应的答案。

输入输出样例 #1

输入 #1

3 3
1 10
5 5
11 31

输出 #1

2
0
4

输入输出样例 #2

输入 #2

5 4
1 20
17 17
1 3
89 100

输出 #2

2
1
0
1

说明/提示

在样例 #1 中，$D=3$。区间 $[1,10]$ 内的合格数为 $3$ 和 $7$，所以第一行答案为 $2$。虽然 $5$ 是奇素数，但 $(5+3)/2=4$ 不是素数，因此第二行答案为 $0$。

在样例 #2 中，$D=5$。区间 $[1,20]$ 内的合格数为 $5$ 和 $17$。