// vipsharmavip 
#include<bits/stdc++.h>
using namespace std;
int prime[1000001];
vector< pair< int , pair< int , int > > > input;
vector< int > store;
void seive(){
   for(int i = 1 ; i <= 1e6 ; ++i ) prime[i] = i;
   for(int i = 2 ; i * i <= 1e6 ; ++i ){
        if(prime[i] == i)
          for(int j = i + i ; j <= 1e6 ; j += i )
          	 if(prime[j] == j)
            prime[j] =  i;
   }
}
void factorize(int x , int index){
     int flag = -1;
     while(x > 1){
       int Pr = prime[x];
       if(flag == -1)
        input.push_back({Pr , {index , 1}}); else {
        if(input.back().first == Pr) 
        	input.back().second.second++; else 
        input.push_back({Pr , {index , 1}});
    }
       x /= prime[x];
       flag = 1;
     }     
}
struct persistent{
      int data;
      persistent *left;
      persistent *right;
       persistent(int _data , persistent *_left , persistent *_right) {
          data = _data;
          left = _left;
          right = _right;
       }
};
persistent *update(persistent *a , persistent *b , int l , int r , int idx , int cost){
           if(idx >= l && idx <= r ){
                   b = new persistent(cost , 0 , 0);
                   if(a)
                   b->data += a->data;
                   if(l != r){
                       if(a == NULL){
                        b->left = update(a , b->left , l , (l + r)/2 , idx  , cost );
                        b->right = update(a , b->right , (l + r)/2 + 1 , r , idx , cost );
                       } else {
                        b->left = update(a->left , b->left , l , (l + r)/2 , idx , cost );
                        b->right = update(a->right , b->right , (l + r)/2 + 1 , r , idx , cost );
                        }
                   }
                   return b;
            }
            else
            return a;
}
int query(persistent *a , int l , int r , int s , int e ){
       if(a == NULL  ||  ( s > r  ||  l > e || s > e ) )
         return 0;
         if(l >= s && r <= e )
         return  a->data;
         return query(a->left , l , (l + r)/2 , s , e ) + query(a->right , ( l + r)/2 + 1 , r , s , e);
}
persistent *segment[2000001];
int main(){
                          seive();
                          int N;
                          scanf("%d",&N);
                          for(int i = 1 ; i <= N ; ++i ){
                              int x;
                              scanf("%d",&x);
                              factorize(x , i);
                          }
                          sort( input.begin() , input.end() );
                          segment[0] = new persistent(0 , 0 , 0);
                          int sz = input.size();
                          for(int i = 0 ; i < input.size() ; ++i ){
                          segment[i + 1] = update(segment[i] , segment[i + 1] , 1 , sz , input[i].second.first , input[i].second.second );
                          store.push_back(input[i].first);
                          }
                          int Q;
                          scanf("%d",&Q);
                          while(Q--){
                          int l , r , x , y;
                          scanf("%d%d%d%d",&l, &r, &x, &y);
                          int idx1 = lower_bound(store.begin() , store.end() , x) - store.begin();
                          int idx2 = upper_bound(store.begin() , store.end() , y) - store.begin();
                          int res1 =  query(segment[idx2] , 1 , sz , l , r);
                          int res2 =  query(segment[idx1] , 1 , sz , l , r);
                          printf("%d\n",res1 - res2);
                          }
                          return 0;
}