#include <bits/stdc++.h>
using namespace std;
const int MAXSIZE = 10000000;
int cnt[MAXSIZE + 100], s[MAXSIZE + 100];
bool mark[MAXSIZE + 100];
void init() {
  for (int i = 2; i <= MAXSIZE; i++) {
    s[i] = s[i - 1];
    if (!mark[i]) {
      for (int j = i; j <= MAXSIZE; j += i) {
        s[i] += cnt[j];
        mark[j] = true;
      }
    }
  }
}
int main() {
  int n, m, l, r, t;
  cin >> n;
  while (n--) cin >> t, cnt[t]++;
  init();
  cin >> m;
  while (m--) {
    cin >> l >> r;
    cout << s[min(r, MAXSIZE)] - s[min(l - 1, MAXSIZE)] << endl;
  }
  return 0;
}
