#include <bits/stdc++.h>
using namespace std;
long long M;
long long const MAX = 1e7 + 1;
vector<long long> is_prime, primes, keys;
map<long long, long long> score_prefix;
long long coun[MAX], score[MAX];
void prep() {
  long long i, j;
  is_prime.assign(M + 2, 0);
  for (i = 2; i <= M; i++) {
    if (is_prime[i] == 1) continue;
    primes.push_back(i);
    if (coun[i] > 0) {
      if (score[i] == 0) keys.push_back(i);
      score[i] += coun[i];
    }
    for (j = 2 * i; j <= M; j += i) {
      is_prime[j] = 1;
      if (coun[j] > 0) {
        if (score[i] == 0) keys.push_back(i);
        score[i] += coun[j];
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  long long i, j;
  vector<long long> v(n, 0);
  M = 0;
  memset(coun, 0, sizeof(coun));
  memset(score, 0, sizeof(score));
  for (i = 0; i < n; i++) {
    cin >> v[i];
    M = max(v[i], M);
    coun[v[i]]++;
  }
  prep();
  long long prev = 0;
  for (i = 0; i < keys.size(); i++) {
    score_prefix[keys[i]] = prev + score[keys[i]];
    prev = score_prefix[keys[i]];
  }
  long long m;
  cin >> m;
  for (i = 0; i < m; i++) {
    long long x, y;
    cin >> x >> y;
    vector<long long>::iterator two = upper_bound(keys.begin(), keys.end(), y),
                                one = lower_bound(keys.begin(), keys.end(), x);
    long long index1 = one - keys.begin();
    long long index2 = two - keys.begin();
    index1--;
    index2--;
    cout << score_prefix[keys[index2]] - score_prefix[keys[index1]] << endl;
  }
  return 0;
}
