Prime Sum Queries

You are given an array of N integers and Q queries. For each query, your task is to compute the sum of all prime numbers in the subarray from index L to R (inclusive).

A prime number is defined as an integer greater than 1 that has no divisors other than 1 and itself. In mathematical notation, a number \( n \) is prime if \( n > 1 \) and if for every integer \( k \) such that \( 2 \leq k \leq \sqrt{n} \), it holds that \( n \mod k \neq 0 \).

You need to process each query and output the resulting sum on a new line.

inputFormat

The first line contains two integers N and Q, where N is the number of elements in the array and Q is the number of queries.

The second line contains N space-separated integers representing the array elements.

Each of the next Q lines contains two integers L and R, representing the starting and ending indices of the subarray for the query (0-indexed).

outputFormat

For each query, output a single line containing the sum of all prime numbers in the specified subarray.

## sample

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

5
10

</p>