#include <bits/stdc++.h>
using namespace std;
int N, arr[1000001], era[10000001], b[10000001], cnt, f[10000001], l, r, T;
vector<int> p;
int main() {
  ios_base ::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  for (int i = 2; i <= 10000000; i++) {
    if (!era[i]) {
      p.push_back(i);
      era[i] = 2;
      for (int j = 2 * i; j <= 10000000; j += i) era[j] = 1;
    }
  }
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> arr[i];
    int u = arr[i], cnt = 0, o = 0;
    while (1) {
      if (u == 1 || p[cnt] * p[cnt] > arr[i]) break;
      if (u % p[cnt] == 0) {
        u /= p[cnt];
        if (!o) f[p[cnt]]++, o = 1;
      } else
        cnt++, o = 0;
    }
    if (era[u] == 2) f[u]++;
  }
  cin >> T;
  for (int i = 1; i <= 10000000; i++) b[i] = b[i - 1] + f[i];
  while (T--) {
    cin >> l >> r;
    l = min(l, 10000000), r = min(r, 10000000);
    cout << b[r] - b[l - 1] << "\n";
  }
}
