#include <bits/stdc++.h>
using namespace std;
const int N = 1e7 + 11, mod = 1e9 + 7;
const double EPS = 1e-7;
const int INF = 2e9;
const int base = 500;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int n, a[N], m, l, r;
long long pref[N], f[N], ct[N];
bool pr[N];
int main() {
  if (fopen("queue"
            ".in",
            "r"))
    freopen(
        "queue"
        ".in",
        "r", stdin),
        freopen(
            "queue"
            ".out",
            "w", stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    ++ct[a[i]];
  }
  memset(pr, 1, sizeof pr);
  for (int i = 2; i <= 1e7 + 11; ++i) {
    if (pr[i]) {
      for (int j = i; j <= 1e7 + 11; j += i) {
        if (j >= i * i) {
          pr[j] = 0;
        }
        f[i] += ct[j];
      }
    }
  }
  for (int i = 2; i <= 1e7 + 11; ++i) {
    pref[i] = pref[i - 1] + f[i];
  }
  cin >> m;
  while (m--) {
    cin >> l >> r;
    if (l > 1e7) {
      cout << "0\n";
      continue;
    }
    if (r > 1e7) {
      cout << pref[10000000] - pref[l - 1] << "\n";
      continue;
    }
    cout << pref[r] - pref[l - 1] << "\n";
  }
  return 0;
}
