32643번 - 정민이의 수열 제조법

문제

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

• 수열에 있는 한 정수를 제곱한 수를 수열에 추가한다.
• 수열에 있는 두 정수를 곱한 수를 수열에 추가한다.

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

익준이의 질문에 답을 해주자.

입력

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

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

출력

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

제한

노트

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