Prime Sum Queries

You are given an array of n integers and q queries. Each query consists of two integers, L and R (1-indexed), and your task is to calculate the sum of all prime numbers in the subarray from index L to R (both inclusive).

Let \(nums\) be the array and \(isPrime(x)\) be a function that checks if \(x\) is prime. You should precompute a prefix sum array \(P\) where: \[ P(i) = \sum_{j=1}^{i} \begin{cases} nums[j] & \text{if } nums[j] \text{ is prime}\\ 0 & \text{otherwise} \end{cases} \] Then, the sum for a query \([L, R]\) is given by: \[ S(L,R)=P(R)-P(L-1) \]

Make sure your solution reads from standard input and writes to standard output.

inputFormat

The input is given in the following format:

N
nums[1] nums[2] ... nums[N]
Q
L1 R1
L2 R2
... 
LQ RQ

Where:

• N is the number of elements in the array.
• The second line contains N integers separated by spaces.
• Q is the number of queries.
• Each of the next Q lines contains two integers L and R, representing a query.

outputFormat

For each query, output one integer on a new line representing the sum of prime numbers in the subarray from index L to R.

## sample

10
2 3 4 5 6 7 8 9 10 11
5
1 3
4 7
1 10
5 5
6 10

5
12
28
0
18

</p>