Số T-Prime là số có đúng 3 ước. 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ố T-Prime. Ví dụ: Cho N=40, x=3, y =30, dãy số từ 1 đến 40. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 30 có tất cả 2 số T-Prime là: 9 và 25.

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ố T-Prime từ vị trí ~x~ đến vị trí ~y~ trong dãy.

Dữ liệu vào:

• Dòng đầu ghi 2 số ~N~, ~q~ (~1 ≤ N \le 10^7~, ~q≤10^5~).
• ~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(~1≤ x \le y \le N~).

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ố T-Prime từ ~x~ đến ~y~ trong dãy trên.

Ví dụ:

Input

40 3
1 3
1 30
3 10

Output

0
3
2