If you study at NSIT then its quite rare for competitive programmers to not hear about Yash Mittal.He is indeed an incredible coder (Beleive me he really is :p). After a while he got bored and now he wants a girlfriend. But of course since he is an extremely good coder, he want his girlfriend also to be atleast a pretty decent coder.For that he is interviewing several girls .The first round of the recruitment procedure will be a coding task. The task is as follows:- Given an array A consisting of N integers and Q queries (Yash Mittal likes queries) where each query is of the form L R .The answer to each query is the number of unique prime numbers inside the array from L to R where L and R are the indexes of the array. Can you solve this task?

Input First line consists of two integers N and Q denoting the number of integers in the array and the number of queries respectively.

The second line consists of N space separated integers denoting the array elements of the array A.

Next Q lines consists of two space separated integers L R denoting the query as described above.

Output

For each query output a single integer denoting the answer as described above.

Constraints

1<=N<=100000

1<=Q<=100000

1<=A[i]<=100000

1<=L<=R<=N

Subtask 1 (10 points): 1<=N,Q<=20

Subtask 2 (20 points ): 1<= N<=1000, 1<=Q<=10000

Subtask 3 (70 points ) : 1<=N,Q<=100000