양의 정수 $N$에 대해, 아래와 같은 쿼리 $Q$개를 처리하는 프로그램을 작성하여라.

• $l$ $r$ : 폐구간 $[l, r]$ 에 속하는 정수 $i$에 대해 $p_i$를 $i$의 소인수의 개수라고 할 때, $\sum\limits_{i=l}^r p_i$ 의 값을 출력한다.

정수 $i$가 소수의 제곱 꼴의 곱으로 표현되는 경우, 각각을 별개로 본다. 예를 들어 $72$의 경우 $2^3 \times 3^2$로 표현할 수 있을 것이다. 그러나 각각을 별개로 봐야 하므로 $2 \times 2 \times 2 \times 3 \times 3$ 에서 $p_{72} = 5$가 된다.

첫째 줄에 $N$과 $Q$가 공백으로 구분되어 주어진다. $(2 ≤ N ≤ 3 \times 10^6; 1 ≤ Q ≤ 2 \times 10^5)$

둘째 줄부터 $Q$개의 줄에 걸쳐 $l, r$이 공백으로 구분되어 주어진다. $(2 ≤ l ≤ r ≤ N)$