No submission language available for this problem.

Background

素数是指只能被 $1$ 和它本身整除的正整数。素数在数学中有着重要的地位，因为它们是构成其他数的基本单元。素数的研究历史悠久，有很多有趣的故事和趣闻。小码君想数一下在一个区间中有多少个素数，但是一个个数太费劲了，你帮小码君写一个程序来计算某个区间 $[L, R]$中素数的个数。

Description

将给定一个整数 $N$ ，需要对 $1$~$N$ 中的素数进行统计。统计完成后，将对统计结果进行 $q$ 次询问，每次询问一段区间 $[L, R]$ 中素数的个数。

Format

Input

第一行两个整数 $N$，$q$

第二行开始的 $q$ 行，每行两个整数 $L$ , $R$

Output

输出共 $q$ 行，每行一个整数表示询问的区间中，素数的个数。

Samples

10 2
1 10
3 4

4
1

Limitation

$1 \leq q \leq 10^5$

$1 \leq N \leq 10^6$

$1\leq L \leq R \leq N$