#include <bits/stdc++.h>
using namespace std;
const long long N = 10000003;
bool prime[N];
long long cnt[N + 6];
long long mp[N + 1];
void seive() {
  for (long long i = 2; i < N; i += 2) cnt[2] += mp[i];
  for (long long i = 3; i < N; i += 2) {
    if (!prime[i]) {
      for (long long j = i; j < N; j += i) {
        cnt[i] += mp[j];
        prime[j] = true;
      }
    }
  }
  for (long long i = 2; i < N - 1; i++) {
    cnt[i] += cnt[i - 1];
  }
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n;
  cin >> n;
  long long mn = 1e8, mx = 0;
  long long a;
  for (long long i = 0; i < n; i++) {
    cin >> a;
    mp[a]++;
  }
  seive();
  long long m, l, r;
  cin >> m;
  while (m--) {
    cin >> l >> r;
    r = min(r, (long long)1e7);
    l = min(l, (long long)1e7);
    cout << cnt[r] - cnt[l - 1] << endl;
  }
}
