#include <bits/stdc++.h>
using namespace std;
long long d[10000005];
int snt[664600], dem;
bool p[10000005];
void sieve() {
  int i, j;
  snt[0] = 2, dem = 1;
  p[0] = p[1] = true;
  for (i = 4; i <= 1e7; i += 2) p[i] = true;
  for (i = 3; i <= 3163; i += 2)
    if (!p[i]) {
      snt[dem++] = i;
      for (j = i * i; j <= 1e7; j += i) p[j] = true;
    }
  for (; i <= 1e7; i += 2)
    if (!p[i]) snt[dem++] = i;
}
void factor(int x) {
  int i;
  if (!p[x]) {
    d[x]++;
    return;
  }
  for (i = 0; i < dem && snt[i] * snt[i] <= x; i++)
    if (x % snt[i] == 0) {
      d[snt[i]]++;
      while (x % snt[i] == 0) x /= snt[i];
    }
  if (x != 1) d[x]++;
}
void input() {
  int i, n, l, r, x, nq;
  sieve();
  scanf("%d", &n);
  for ((i) = 0; (i) < (n); (i)++) scanf("%d", &x), factor(x);
  for ((i) = (3); (i) <= (10000000); (i)++) d[i] += d[i - 1];
  scanf("%d", &nq);
  while (nq--) {
    scanf("%d %d", &l, &r);
    l = ((l) < (10000000) ? (l) : (10000000));
    r = ((r) < (10000000) ? (r) : (10000000));
    printf("%I64d\n", d[r] - d[l - 1]);
  }
}
int main() {
  input();
  return 0;
}
