#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10000002], num[10000002];
bool prim[10000002];
int main() {
  int x;
  int l, r;
  while (cin >> n) {
    int maxv = 0;
    for (int i = 1; i <= n; ++i) {
      cin >> x;
      a[x]++;
      maxv = max(maxv, x);
    }
    for (int i = 2; i <= maxv; ++i) {
      num[i] = num[i - 1];
      if (!prim[i]) {
        for (int j = i; j <= maxv; j += i) {
          num[i] += a[j];
          prim[j] = true;
        }
      }
    }
    cin >> m;
    while (m-- > 0) {
      cin >> l >> r;
      l = min(l - 1, maxv);
      r = min(r, maxv);
      cout << num[r] - num[l] << endl;
    }
  }
  return 0;
}
