#include <bits/stdc++.h>
using namespace std;
long long n, fix[10000005], a[10000005], k, res[10000005], i, j, f = 0;
map<long, long> mp;
int main() {
  ios::sync_with_stdio(0);
  cin >> n;
  for (i = 2; i <= 10000000; i++) {
    if (fix[i] == 0) {
      fix[i] = i;
      for (j = i * i; j <= 10000000; j += i) {
        fix[j] = i;
      }
    }
  }
  for (i = 0; i < n; i++) {
    cin >> a[i];
    f = max(f, a[i]);
    k = a[i];
    while (k >= 2) {
      if (mp[fix[k]] == 0) {
        res[fix[k]]++;
        mp[fix[k]] = 1;
      }
      k = k / fix[k];
    }
    mp.clear();
  }
  for (i = 1; i <= 10000000; i++) {
    res[i] = res[i - 1] + res[i];
  }
  long long m, x, y;
  cin >> m;
  for (i = 0; i < m; i++) {
    cin >> x >> y;
    if (x > y) {
      cout << 0 << endl;
      continue;
    }
    if (x <= 10000000 && y > f) {
      cout << res[f] - res[x - 1] << endl;
      continue;
    }
    if (x > 10000000 && y > 10000000) {
      cout << 0 << endl;
      continue;
    }
    cout << res[y] - res[x - 1] << endl;
  }
}
