Jeongmin's Sequence Recipe

Time limit1sMemory limit1024 MB

Summary

For each query [a, b], count the starting integers in range, where the starting set is 1 plus all primes up to N.

Level: Medium4 of 10
Topics: Math, Number theory, Prefix sum
Solved: No attempts yet

문제

Jeongmin wants to build a sequence that contains each integer from 1 to $N$ exactly once. To do this, he prepared a sequence of positive integers with the smallest possible count, then repeated the following operations until he reached the goal.

Add the square of an integer in the sequence to the sequence.
Add the product of two integers in the sequence to the sequence.

After finishing all the operations, Ikjun asked Jeongmin which integers he had started with. Instead of answering, Jeongmin said that whenever Ikjun gives $a$ and $b$ , he would tell the number of initial integers between $a$ and $b$ , inclusive. Ikjun will ask $M$ questions in total.

Answer Ikjun's questions.

입력

The first line contains integers $N$ and $M$ , separated by a space. ( $1 \le N \le 5000000$ ; $1 \le M \le 1000000$ )

From the second line, $M$ lines follow, each containing integers $a$ and $b$ separated by a space. ( $1 \le a \le b \le N$ )

출력

Print the answer to each question on its own line, $M$ lines in total.

힌트

Python 3 users are recommended to submit with PyPy3.

Examples2

Example 1
Input
```
50 4
1 15
5 6
20 40
40 50
```
Expected output
```
7
1
4
3
```

Example 2

Input

Expected output