Recently, the bear started studying data structures and faced the following problem.

You are given a sequence of integers *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> of length *n* and *m* queries, each of them is characterized by two integers *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>. Let's introduce *f*(*p*) to represent the number of such indexes *k*, that *x*<sub class="lower-index">*k*</sub> is divisible by *p*. The answer to the query *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> is the sum: <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/5e448f6c1a0e40843cecdbbeb95970464626032f.png" style="max-width: 100.0%;max-height: 100.0%;"/>, where *S*(*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>) is a set of prime numbers from segment [*l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub>] (both borders are included in the segment).

Help the bear cope with the problem.
The first line contains integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>). The second line contains *n* integers *x*<sub class="lower-index">1</sub>, *x*<sub class="lower-index">2</sub>, ..., *x*<sub class="lower-index">*n*</sub> (2 ≤ *x*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">7</sup>). The numbers are not necessarily distinct.

The third line contains integer *m* (1 ≤ *m* ≤ 50000). Each of the following *m* lines contains a pair of space-separated integers, *l*<sub class="lower-index">*i*</sub> and *r*<sub class="lower-index">*i*</sub> (2 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ 2·10<sup class="upper-index">9</sup>) — the numbers that characterize the current query.
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	map<int,int> check_arr_exists;
	map<int,int>::iterator it_intint;

	int n;cin>>n;
	int max_snt = -1;
	for(int i = 0;i<n;i++){
        int t;cin>>t;
        check_arr_exists[t]++;
        if(t>max_snt) max_snt = t;
	}
	int num_ts;cin>>num_ts;
	vector<pair<int,int> > pair_check;
	vector<pair<int,int> >::iterator it_v_p_ii;
	for(int i = 0;i<num_ts;i++){
        int a,b;cin>>a>>b;
        pair_check.push_back({a,b});
    }

    bool CHECK_SNT[max_snt+1];
    for(int i = 0;i<=max_snt;i++){
        CHECK_SNT[i]= true;
    }
    CHECK_SNT[0] = false;
    CHECK_SNT[1] = false;

    map<int,int> value_ans;

    for(int i = 2;i<=max_snt;i++){
        if(CHECK_SNT[i]==true){
            if(check_arr_exists[i]!=0) value_ans[i]+=check_arr_exists[i];
            for(int j = 2*i;j<=max_snt;j+=i){
                CHECK_SNT[j] = false;
                if(check_arr_exists[j]!=0) value_ans[i]++;
            }

        }
    }

//    for(it_intint = value_ans.begin();it_intint!=value_ans.end();++it_intint){
//        cout<<it_intint->first<<" "<<it_intint->second<<endl;
//    }

    for(int i = 0;i<pair_check.size();i++){
        int ans = 0;
        for(int j = pair_check[i].first;j<=pair_check[i].second && j<=max_snt;j++){
            ans+=value_ans[j];
        }
        cout<<ans<<endl;
    }

	return 0;
}
