#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e7+5;
ll freq[maxn],ans[maxn],arr[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    ll n,m;
    cin>>n;
    for(ll i=1; i<=n; i++)
    {
        ll p;
        cin>>p;
        freq[p]++;
    }
    for(ll i=2; i<maxn; i++)
    {
        arr[i]=arr[i-1];
        if(ans[i])
            continue;
        arr[i]+=freq[i];
        for(ll j=i+i; j<maxn; j+=i)
        {
            ans[j]=1;
            arr[i]+=freq[j];
        }
    }
    cin>>m;
    for(ll i=1; i<=m; i++)
    {
        ll l,r;
        cin>>l>>r;
        r =min(maxn-1,r);
        l =min(maxn-1,l-1);
        cout<<arr[r]-arr[l]<<endl;
    }
}