#include <bits/stdc++.h>
using namespace std;
long prime[10000001];
long pre[10000001];
long cal[10000001];
long h = 1e7 + 1, j;
long min(long x) {
  if (x >= 1e7) {
    return 1e7;
  }
  return x;
}
int main() {
  std::ios::sync_with_stdio(false);
  long i, n, t, m, a, b;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> t;
    cal[t]++;
  }
  for (i = 2; i < h; i++) {
    if (prime[i] == 0) {
      for (j = i; j < h; j += i) {
        prime[j] = -1;
        pre[i] += cal[j];
      }
    }
  }
  for (i = 1; i < h; i++) {
    pre[i] += pre[i - 1];
  }
  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> a >> b;
    a = min(a);
    b = min(b);
    cout << pre[b] - pre[a - 1] << endl;
  }
}
