Sum of Prime Numbers in Range

You are given an array \(A\) of \(n\) integers and \(q\) queries. For each query, which is given as two integers \(L\) and \(R\) (1-indexed), you are required to compute the sum of all prime numbers in the subarray \(A[L \ldots R]\). A number \(x\) is prime if and only if \(x\) has exactly two distinct positive divisors: 1 and \(x\). Use the efficient Sieve of Eratosthenes algorithm to precompute prime numbers up to the maximum value in \(A\), and then use a prefix sum approach to answer the queries quickly.

Note: The indices of array are 1-indexed. That is, the first element of \(A\) is at index 1.

Example:

Input:
5
2 3 4 5 6
3
1 3
2 5
1 5
Output:
5
8
10

</p>

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer \(n\), the number of elements in the array \(A\).
2. The second line contains \(n\) space-separated integers representing the elements of \(A\).
3. The third line contains an integer \(q\), the number of queries.
4. The next \(q\) lines each contain two space-separated integers \(L\) and \(R\), representing the bounds (inclusive) of the query.

outputFormat

For each query, output a single integer on a new line representing the sum of all prime numbers in the subarray \(A[L \ldots R]\).

## sample

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

5
8
10

</p>