Prime Interval Sum

You are given an array of n integers and several queries. For each query, you are provided with two indices l and r. Your task is to compute the sum of the elements in the subarray from index l to r (inclusive), denoted by \(S_{l,r} = \sum_{i=l}^{r} a_i\), and determine if this sum is a prime number.

A number \(p\) is called prime if \(p > 1\) and its only positive divisors are 1 and \(p\). Otherwise, it is not prime. Use an efficient method to check for prime numbers because the sum can be very large.

The input is processed from standard input and the result for each query should be printed on a new line to standard output. Good luck!

inputFormat

The input is given via standard input in the following format:

n
a1 a2 ... an
q
l1 r1
l2 r2
... 
lq rq

Where:

• n is the number of elements in the array.
• a1, a2, ..., an are the elements of the array.
• q is the number of queries.
• Each of the next q lines contains two integers, l and r, representing the indices (1-indexed) of the subarray.

outputFormat

For each query, output a single line containing either Prime if the sum of the subarray \(S_{l,r}\) is a prime number, or Not Prime otherwise.

## sample

6
6 1 3 7 5 8
3
1 3
2 6
4 4

Not Prime
Not Prime
Prime

</p>