#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mem(a,b) memset((a),(b),sizeof(a))

const int INF=0x3f3f3f3f;

const int N=1e6+;

const int M=1e7+;

int  vis[M]={};

bool not_prime[M]={false};

int dp[M]={};

void prime()

{

    for(int i=;i<M;i++)

    {

        if(!not_prime[i])

        {

            dp[i]+=vis[i];

            for(int j=i+i;j<M;j+=i)

            not_prime[j]=true,dp[i]+=vis[j];

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int n,x;

    cin>>n;

    for(int i=;i<n;i++)

    {

        cin>>x;

        vis[x]++;

    }

    prime();

    for(int i=;i<M;i++)dp[i]+=dp[i-];

    int m,l,r;

    cin>>m;

    while(m--)

    {

        cin>>l>>r;

        if(l>M)l=M-;

        if(r>M)r=M-;

        cout<<dp[r]-dp[l-]<<endl;

    }

    return ;

}