Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Cho số nguyên dương ~N~. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số liên tiếp từ 1 đến N có bao nhiêu số nguyên tố. Ví dụ: Cho N=10, x=3, y =6, dãy số từ 1 đến 10. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 2 số nguyên tố là: 3 và 5.

Yêu cầu: Cho số nguyên dương ~N~, ứng với mỗi cặp số ~x~, ~y~ hãy in ra số lượng các số nguyên tố từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~.
• ~q~ dòng tiếp theo, mỗi dòng ghi 2 số nguyên ~x~, ~y~ tương ứng vị trí ~x~ và vị trí ~y~ trong dãy trên (~0≤x \le y \le N,q≤10^6~).

Kết quả:

• Gồm ~q~ dòng, mỗi dòng ghi 1 số nguyên dương là số lượng các số nguyên tố từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

10 3
1 3
3 6
3 7

Output

2
2
3