You are given a 1 based indexed array of n numbers. Now you will be asked q queries. In each query you will be given l and r . You have to ouput F(A[l]) + F(A[l+1]) + . . . . . . . F(A[R]).

F(A[i]) = Sum of g(d) where d is divisor of A[i]
g(d) = total numbers which are less than or equal to d and are coprime to d

Input:
First line consists of two space separated integers denoting n and q.
Second line consists of n space separated integers denoting the array.
Following q lines consists of two space separated integers denoting l and r.

Output:
For each query print the required answer in a new line.

Constraints
1<=n<=10^6
1<=L<=R<=n
1<=A[i]<=10^9
1<=q<=10^6