

Rabbit KingdomTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3687 Accepted Submission(s): 1227 Problem Description Long long ago, there was an ancient rabbit kingdom in the forest. Every rabbit in this kingdom was not cute but totally pugnacious, so the kingdom was in chaos in season and out of season. n rabbits were numbered form 1 to n. All rabbits' weight is an integer. For some unknown reason, two rabbits would fight each other if and only if their weight is NOT coprime. Now the king had arranged the n rabbits in a line ordered by their numbers. The king planned to send some rabbits into prison. He wanted to know that, if he sent all rabbits between the ith one and the jth one(including the ith one and the jth one) into prison, how many rabbits in the prison would not fight with others. Please note that a rabbit would not fight with himself. Input The input consists of several test cases. The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries. The following line contains n integers, and the ith integer W_{i} indicates the weight of the ith rabbit. Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the Lth one to the Rth one into prison. (1 <= n, m, W_{i} <= 200000, 1 <= L <= R <= n) The input ends with n = 0 and m = 0. Output For every query, output one line indicating the answer. Sample Input
Sample Output
Hint In the second case, the answer of the 4th query is 2, because only 1 and 5 is coprime with other numbers in the interval [2,6] . Source  
