#include <bits/stdc++.h>
using namespace std;
int const X = 1e7 + 20;
int n, m, l, r, a, cnt[X], ps[X];
bool np[X];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = (int)(0); i < (int)(n); i++) cin >> a, cnt[a]++;
  for (int i = (int)(2); i < (int)(X); i++)
    if (!np[i]) {
      ps[i] += cnt[i];
      for (int j = 2 * i; j < X; j += i) {
        np[j] = 1;
        ps[i] += cnt[j];
      }
    }
  for (int i = (int)(1); i < (int)(X); i++) ps[i] += ps[i - 1];
  cin >> m;
  while (m--) {
    cin >> l >> r;
    l--;
    r = min(r, X - 1), l = min(l, X - 1);
    cout << ps[r] - ps[l] << '\n';
  }
  return 0;
}
