#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <ctime>

 #include <cstdlib>

 #include <vector>

 #include <algorithm>

 using namespace std;

 #define ll long long

 #define N 10001000

 #define M 670000

 #define pii pair<int,int>

 #define lowbit(x) x&(-x)

 int prime[M+] , tot ;

 bool check[N+];

 void get_prim()

 {

     for(int i= ; i<=N ; i++){

         if(!check[i]) prime[tot++] = i;

         for(int j= ; j<tot ; j++){

             if((ll)i*prime[j]>N) break;

             check[i*prime[j]] = true;

             if(i%prime[j]==) break;

         }

     }

 }

 int Hash1(int x)

 {

     if(x>) return ; //664579是10000000内素数的数目

     int l= , r=tot- , ans=;

     while(l<=r){

         int m = (l+r)>>;

         if(prime[m]>=x){ans = m , r=m-;}

         else l=m+;

     }

     return ans+;

 }

 int Hash2(int x)

 {

     if(x>) return ;

     int l= , r=tot- , ans=;

     while(l<=r){

         int m = (l+r)>>;

         if(prime[m]<=x){ans = m , l=m+;}

         else r=m-;

     }

     return ans+;

 }

 ll sum[M];

 void add(int x , int v){for(int i=x ; i<=tot ; i+=lowbit(i)) sum[i] += v;}

 ll query(int x)

 {

     ll ret = ;

     for(int i=x ; i> ; i-=lowbit(i)) ret+=sum[i];

     return ret;

 }

 void fenjie(int x)

 {

     int mx = (int)sqrt(x+0.5);

     for(int i= ; i<tot ; i++){

         if(prime[i]*prime[i]>x) break;

         if(x%prime[i]==){

           //  cout<<"in: "<<i<<" "<<prime[i]<<endl;

             add(i+ , );

             while(x%prime[i]==) x/=prime[i];

         }

     }

     if(x>){

         int pos = lower_bound(prime , prime+tot , x)-prime;

         add(pos+ , );

     }

 }

 int main() {

    // freopen("a.in" , "r" , stdin);

    // freopen("out.txt" , "w" , stdout);

     get_prim();

     int n , m , s , t;

     while(~scanf("%d" , &n))

     {

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

             int x ;

             scanf("%d" , &x);

             fenjie(x);

         }

         scanf("%d" , &m);

         while(m--){

             scanf("%d%d" , &s , &t);

             int p1 = Hash1(s) , p2 = Hash2(t);

           //  cout<<p1<<" "<<p2<<endl;

             printf("%I64d\n" , query(p2)-query(p1-));

         }

     }

 }