#include <bits/stdc++.h>
using namespace std;
const int n_max = 10000005;
int lp[n_max], j, n, x, L, R, Q;
int s[n_max], y;
vector<int> pr;
long long i;
int main() {
  for (i = 2; i <= 10000000; i++) {
    if (!lp[i]) lp[i] = i, pr.push_back(i);
    for (j = 0; j < pr.size() && pr[j] <= lp[i] && i * pr[j] <= 10000000; j++)
      lp[i * pr[j]] = pr[j];
  }
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &x);
    while (x > 1) {
      s[lp[x]]++;
      y = lp[x];
      while (x > 1 && x % y == 0) x /= y;
    }
  }
  for (i = 1; i <= 10000000; i++) s[i] += s[i - 1];
  scanf("%d", &Q);
  while (Q--) {
    scanf("%d%d", &L, &R);
    if (L > 10000000) {
      printf("0\n");
      continue;
    }
    R = (R < 10000000 ? R : 10000000);
    L = (L < 10000000 ? L : 10000000);
    printf("%d\n", s[R] - s[L - 1]);
  }
}
