1753: [본선] 구간에 포함된 소수의 합

n개의 자연수로 이루어진 수열이 주어지고,

i번째 수부터 r번째 수 사이에 있는 수들 중에서 소수(prime number)인 수들의 합을 계산하라는

쿼리 질문을 q번 입력된다. (i번째 수와 r번째 수도 포함된다.)

주어진 시간 동안에 정확한 답을 모두 출력하는 프로그램을 작성해보자.

첫 번째 줄에 n이 주어진다.
둘 번째 줄에 n개의 자연수(a_i)가 공백으로 구분하여 주어진다.
셋 번째 줄에 질문의 개수인 q가 주어진다.
넷 번째 줄부터 q줄에 걸쳐서 l, r이 공백으로 구분하여 차례대로 주어진다.

(1 ≤ n, ai ≤ 1,000,000)

(1 ≤ q ≤ 50)

q개의 줄에 걸쳐 해당 범위에 포함된 소수들의 합을 한 줄에 1개씩 출력한다.

5
1 2 3 4 5
3
1 5
2 3
4 5

10
5
5