Finny the monster wants to greenify his world "Finnyland" .There are N Cities in the world numbered from 1 to N. A city is either polluting or non polluting . Each city has a[i] number of trees in it .If number of trees is prime then the city is polluting else it is non polluting .Now Finny wants to convert polluting cities to non polluting .

There will be Q queries in which Finny will be given two cities L and R ,And he want to find out the number of polluting cities between L and R (including L and R).

Note: Use fast I/O for java.

Input Format:- First line contains an integer N which denotes the number of cities. Second line contains N integers denoting the number of trees a[i] in each city. Third line contains an integer Q denoting the number of queries. Q lines follow each containing two integers L and R the indices of two cities.

Constraints:-

1 <= N <= 100000

1 <= a[i] <= 100000(no of trees in each city)

1 <= Q <= 100000

1 <= L <= R <= N

Output Format:-

Each of the Q lines contains a single integer denoting the number of polluting cities in range [L,R].

Input:-

5

1 2 3 4 5

2

2 3

2 4

Output:-

2

2

Author : Prateek Bhargav Abhishek Jain