정민이의 수열 제조법

정민이는 1부터 $N$까지의 정수가 한 개씩 들어 있는 수열을 만들려고 한다. 이를 위해 최소 개수의 양의 정수가 들어 있는 수열을 준비했고, 목표를 달성할 때까지 다음 작업을 반복했다.

• 수열에 있는 정수 하나를 제곱한 값을 수열에 추가한다.
• 수열에 있는 정수 두 개를 곱한 값을 수열에 추가한다.

모든 작업을 마친 정민이에게 익준이가 처음에 어떤 정수들로 작업을 시작했는지 물었다. 정민이는 답을 알려주는 대신, 익준이가 $a$와 $b$를 물어보면 초기 정수 중 $a$ 이상 $b$ 이하인 정수의 개수를 알려 주겠다고 했다. 익준이는 질문을 총 $M$번 할 것이다.

익준이의 질문에 답하자.

첫 번째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 5000000$; $1 \le M \le 1000000$)

두 번째 줄부터 $M$개의 줄에 정수 $a$, $b$가 공백으로 구분되어 주어진다. ($1 \le a \le b \le N$)

$M$개의 줄에 각 질문의 답을 출력한다.

Python 3 사용자는 PyPy3로 제출할 것을 권장한다.