You will be given an array of n elements. Also you will be given Q queries.

In each query, you will be given two integers, which denotes a range of your given array.

In reply to the query, you have to calculate the number of primes in the range from l’th to r’th index of the given array.

Let me explain with an example.

Let the given array is a and a = {2, 6, 3, 5, 4, 3}.

Now, if you have a query to calculate the number of primes in the range from 2 to 5, then the answer will be 2 and the primes are 3 (in index 3) and 5(in index 4).

Input:

In the first line, you will be given two integers, n and q.

In the next line, you will be given n integers a_1, a_2, a₃…a_n, the elements of the array.

In the next q lines, you will be given two integers, l and r.

Constraint:

 1 <= n, q <= 10⁵

1 <= l, r <= n

1 <= a_i <= 1000 for all i in range 1 to n.

Output:

For each query, print an integer, the number of primes in the range from l to r in a new line.

Sample Input:

6 6

2 4 5 7 9 11

1 3

2 4

1 4

3 6

4 6

2 5

Sample Output:

2

2

3

3

2

2

Explanation:

For the first query, there are two primes from 1^st to 3^rd index, they are 2 and 5.