Sahra là một kế toán tại doanh nghiệp tư nhân do Bobby làm giám đốc. Bobby là một ông chủ rất thích làm từ thiện, ông đã quyết định thu nhập của những ngày nào mang số thứ tự là số nguyên tố sẽ cho các em nhỏ ở vùng khó khăn mua sách vở (nếu thu nhập hôm đó là dương), ngày bắt đầu lập công ty mang số thứ tự là ~1~. Ngoài ra, Bobby rất khắc khe trong công việc và luôn muốn biết thu nhập của công ty trong khoảng thời gian từ ngày thứ ~X~ đến ngày thứ ~Y~. Nhưng ông có một tính rất đãng trí nên luôn hỏi Sahra rất ngẫu hứng. Bạn hãy viết chương trình giúp Sahra tính tổng thu nhập của công ty dựa trên các câu hỏi của Bobby là từ ngày thứ ~X~ đến ngày thứ ~Y~ công ty thu được bao nhiêu (Thu nhập không tính những ngày có số thứ tự là số nguyên tố nếu hôm đó có thu nhập dương).

Yêu cầu: Tính tổng thu nhập của công ty trong khoảng thời gian từ ngày ~X~ đến ngày ~Y~, loại bỏ các ngày có số thứ tự là số nguyên tố nếu thu nhập ngày đó dương.

Input

• Dòng đầu tiên chứa số nguyên ~N~ là số ngày mà công ty đã đi vào hoạt động.
• Dòng thứ 2 chứa ~n~ số nguyên, ~A_i~ tương ứng là thu nhập ngày thứ ~i~ của công ty, mỗi số cách nhau bởi khoảng trắng.
• Dòng thứ 3 chứa số nguyên ~Q~, số truy vấn của Bobby.
• ~Q~ dòng tiếp theo, dòng thứ ~i~ chứa 2 số nguyên ~X_i~ và ~Y_i~ là khoảng truy vấn của Bobby.

Output

• Ghi ra ~Q~ dòng, dòng thứ ~i~ là tổng thu nhập tương ứng với truy vấn thứ ~i~ trong file input, không tính các ngày có số thứ tự là số nguyên tố (nếu thu nhập ngày đó dương).

Sample Input 1

5
-2 5 8 6 9
1
3 5

Sample Output 1

6