题目描述

给定一个范围 $n$, 对于 $q$ 个区间 $[l, r]$, 求区间 $[l, r]$ 内的素数个数

输入格式

第一行包含两个正整数 $n$ , $q$ ，分别表示查询的范围和查询的个数。

接下来 $q$ 行,每行包含 $2$ 个不小于 $1$ 且不大于 $n$ 的整数 $l$, $r$，即询问该区间内的素数个数。

输出格式

$q$行, 输出每个区间内素数个数

样例

Input

10 2
2 5
3 6

Output

3
2

数据范围与提示

对于 $10\%$ 的数据 ,$1 \le n, q \le 10$
对于 $20\%$ 的数据, $1 \le n, q \le 100,000$
对于 $30\%$ 的数据, $1 \le n \le 1000,000, 1 \le q \le 1000$
对于 $20\%$ 的数据, $1 \le n, q \le 1,000,000$
对于 $20\%$ 的数据, $1 \le n, q \le 2,000,000$
请使用较快的 $I/O$ 方式