Prime Subarray Queries

You are given an array of integers and a set of queries. Each query asks for the number of prime numbers in a subarray of the given array, where the subarray is specified by its 1-indexed starting and ending positions.

To solve this problem, you can follow these steps:

1. Use the Sieve of Eratosthenes to generate all prime numbers up to the maximum value in the array. The sieve works in \(O(n \log \log n)\) time.
2. Precompute a prefix sum array \(prefix\) where \(prefix[i]\) stores the count of prime numbers in the array up to the \(i\)-th element. The relation is given by: \[ prefix[i] = prefix[i-1] + \begin{cases} 1 & \text{if } a[i] \text{ is prime} \\ 0 & \text{otherwise} \end{cases} \]
3. For each query defined by indices \(l\) and \(r\), the number of primes in the subarray \(a[l..r]\) is computed as: \[ answer = prefix[r] - prefix[l-1] \]

Implement your solution to read from standard input and write to standard output.

inputFormat

The first line contains two space-separated 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.

The following \(q\) lines each contain two space-separated integers \(l\) and \(r\), representing a query asking for the number of prime numbers in the subarray from index \(l\) to index \(r\) (1-indexed).

outputFormat

For each query, output a single line with one integer: the count of prime numbers in the subarray defined by that query.

## sample

5 3
2 4 5 7 10
1 3
2 5
1 5

2
2
3

</p>