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. Tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~y~ trong dãy đã cho. 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; nên tổng các số nguyên tố có trong đoạn từ 3 đến 6 là: 30

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 tính tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới 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à tổng các số nguyên tố trong đoạn từ vị trí ~x~ tới vị trí ~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

8
8
16