#include <bits/stdc++.h>
using namespace std;
bool isp[10000000 + 5];
vector<int> u, res;
void sieve() {
  isp[0] = isp[1] = 0;
  for (int i = 2; i < 1e7 + 5; i++) isp[i] = 1;
  for (int i = 2; i < 1e7 + 5; i++) {
    if (isp[i]) {
      res[i] += u[i];
      for (int j = 2 * i; j < 1e7 + 5; j += i) isp[j] = 0, res[i] += u[j];
    }
  }
  for (int i = 1; i < res.size(); i++) res[i] += res[i - 1];
}
int main() {
  int n;
  scanf("%d", &n);
  ;
  u.clear();
  u.resize(1e7 + 5, 0);
  res.clear();
  res.resize(1e7 + 5, 0);
  for (int i = 0; i < n; i++) {
    int tmp;
    scanf("%d", &tmp);
    ;
    u[tmp]++;
  }
  sieve();
  int m;
  scanf("%d", &m);
  ;
  while (m--) {
    int l, r;
    scanf("%d", &l);
    ;
    scanf("%d", &r);
    ;
    r = min(r, (int)1e7);
    l = min(l, (int)1e7);
    printf("%d\n", res[r] - res[l - 1]);
    ;
  }
  return 0;
}
