hoangduong là một kế toán tại doanh nghiệp tư nhân do phamgiaminh làm giám đốc. phamgiaminh là một ông chủ rất thích làm từ thiện, nên phamgiaminh đã quyết định: nếu thu nhập của ngày thứ ~i~ là dương, đồng thời ~i~ là số nguyên tố, thì thu nhập ngày ~i~ sẽ cho các em nhỏ ở vùng khó khăn mua sách vở, ngày bắt đầu lập công ty mang số thứ tự là ~1~. Ngoài ra, phamgiaminh rất khắt 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ó tính đãng trí nên luôn hỏi hoangduong rất ngẫu hứng. Bạn hãy viết chương trình giúp hoangduong tính tổng thu nhập của công ty từ ngày thứ ~X~ đến ngày thứ ~Y~ (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).

INPUT

Dòng đầu tiên chứa số nguyên ~N~ ~(N \le 10^5)~ 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~ ~(A_i \le 10^5)~, 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~ ~(Q \le 10^5)~, số truy vấn của phamgiaminh.

~Q~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~X~ và ~Y~ ~(1 \le X,~ ~Y \le N)~ là khoảng truy vấn của phamgiaminh.

OUTPUT

Gồm ~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ố.

SAMPLE INPUT 1

5
-2 5 8 6 9
1
3 5

SAMPLE OUTPUT 1

6

SAMPLE INPUT 2

10
-2 5 8 6 9 -3 -5 6 8 10
3
1 3
5 9
1 10

SAMPLE OUTPUT 2

-2
6
20