Let us first describe a Complex Function.

Complex Function(vector < int> array) {

    int minimum=1e9;
    for(int a:array){
            minimum=min(minimum,a);
    }
    for(int i=minimum;i>=1;i--){
            bool flag=true;
            for(int a:array){
                    if((a%i)>0)
                        flag=false;
            }
            if(flag==true)
                return i;
    }

}

So the complex function receives a vector and return an integer for that array. Let us call this integer(value returned by the function) as complex value of that array.

Rahul and Sandeep were having coffee this weekend when Sandeep introduced him to this Complex Function. Rahul loved maths. So he got excited on seeing this function. But Sandeep couldn't see Rahul's happiness. So to make his life even worse he asked him an even tougher problem that involved this Complex Function.

Sandeep gave Rahul an array consisting of N integers. He then asked Rahul to compute the complex value of all the subarrays of that array. Something like if Rahul had an array consisting of 2 integers. He asked him to calculate Complex(a[1:1]), Complex(a[2:2]), Complex(a[1:2]). After he did that, Sandeep started shooting queries on Rahul. In each query he gave him two integers L and R and asked him to tell him the total number of subarray such that their complex value lies between L and R (both included).

Rahul had no idea how to solve this problem efficiently. So he turns to you for help. Help Rahul in tackling Sandeep's problem.

Input:

The first line contains N denoting the size of array. This is followed by N space separated integers that denote the elements present in the array. After this line we have an integer Q that indicates the count of queries. Finally we have Q lines, each line containing two integers L and R.

Output:

Output Q lines, each line containing the answer of Sandeep's query.

Constraints:

1 <= N <= \(10^5\)

1 <= Array Elements <= \(10^9\)

1 <= Q <= \(2*10^5\)

1 <= L <= R <= \(10^9\)