소수와 쿼리

문제

정수 $x$가 $1$보다 크고, $1$과 자기 자신을 제외한 양의 약수를 가지지 않으면 $x$를 소수라고 한다.

정수 $N$과 $Q$개의 쿼리가 주어진다. 각 쿼리는 두 정수 $i$, $j$로 이루어져 있으며, $i$ 이상 $j$ 이하인 정수 중 소수의 개수를 묻는다.

각 쿼리마다 구간 $[i, j]$에 포함된 소수의 개수를 출력하시오.

입력

첫째 줄에 두 정수 $N$과 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 1,000,000; 1 \le Q \le 200,000)$

다음 $Q$개의 줄 중 $k$번째 줄에는 하나의 쿼리를 나타내는 두 정수 $i_k$, $j_k$가 공백으로 구분되어 주어진다. $(1 \le i_k \le j_k \le N)$

출력

각 쿼리마다 구간 $[i_k, j_k]$에 포함된 소수의 개수를 한 줄에 하나씩 출력한다.

예제 입력 1

10 4
1 10
2 2
3 7
8 10

예제 출력 1

4
1
3
0

예제 입력 2

20 5
1 1
1 2
10 20
11 19
14 16

예제 출력 2

0
1
4
4
0