Ygritte always claims that Jon Snow knows nothing. To prove her wrong, Jon is planning to solve a tough question. Help Jon in the endeavour.
Proper divisors of a positive number are the divisors of the number except the number itself. For example, proper divisors of 12 are 1,2,3,4,6.
Given an array of size N and Q queries. Let Ai denote the ith element in the array(0-based indexing throughout the question). Each query is of the form L R. For each query find the count of distinct sums of proper divisors in the range L to R. See the sample input and output for better explanation.
NOTE : Consider sum of proper divisor of 0 as 1.
Constratints:
1 <= N <= 105
0 <= Ai <= 105
1 <= Q <= 105
0 <= L <= R <= N-1
Input:
The first line contains two integers, N and Q. The next line contains N integers corresponding to Ai. The next Q lines contains two integers each, L and R.
Output:
Print Q lines, the ith line denoting the answer to the ith query.
For the first query, the numbers are [10,159] and their respective sums of proper divisors are [8,57]. Thus distinct elements are 2.
For the second query, the numbers are [559,10,159] and their respective sums of proper divisors are [57,8,57]. Thus distinct elements are 2.
For the third query, the numbers are [6,8,559] and their respective sums of proper divisors are [6,7,57]. Thus distinct elements are 3.
