Nam rất thích làm từ thiện, Là CEO của công ty XYZ, thế nên Nam đưa ra quy định cho công ty mình: những ngày nào mang số thứ tự là số nguyên tố sẽ cho thu nhập ngày đó 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, Nam 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.

Yêu cầu: Tính tổng thu nhập của công ty dựa trên quy định của công ty từ ngày x thứ đế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).

Dữ liệu vào:

• 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ứ hai chứa n số nguyên, a[i] tương ứng là thu nhập ngày thứ i của công ty;

• Dòng thứ ba chứa số nguyên q là số truy vấn của Nam;

• q dòng tiếp theo, dòng thứ i chứa hai số nguyên x[i] và y[i] là khoảng truy vấn của Nam.

Dữ liệu ra:

Gồm q dòng, dòng thứ i là kết quả của truy vấn thứ i.

Sample Input

5
-2 5 8 6 9
1
3 5

Sample Output

6

Sample Input

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

Sample Output

-2
6
20

Giới hạn:

1 ≤ n, q ≤5*10^4; |a[i]|<=42000; 1 ≤ x[i] ≤ y[i] ≤ n.