Số nguyên tố là số chỉ có 2 ước số 1 và chính nó. Nam đố Quân bài toán sau: Cho dãy số gồm ~N~ số nguyên dương, các số trong dãy được đánh số bắt đầu từ 1. Đếm trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy số đó có bao nhiêu số nguyên tố. Ví dụ: Cho N=7, x=3, y =6, dãy số 3, 6, 2, 17, 11, 22, 19. Trong đoạn từ vị trí thứ 3 đến vị trí thứ 6 có tất cả 3 số nguyên tố là: 2, 17, 11.

Yêu cầu: Cho dãy gồm có ~N~ số nguyê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~ (~0≤N,q≤10^5~).
• Dòng 2: ghi giá trị dãy số ~a_1,a_2,…a_N~ (~1≤a_i≤10^7~) các số cách nhau một dấu cách.
• ~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.

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

7 3
1 3 5 6 8 9 11
1 3
2 6
3 7

Output

2
2
2