#include <bits/stdc++.h>
char isNotP[10000000 + 1];
int p[700000] = {2}, len_p = 1;
int num_factor[10000000 + 1];
void sieve(void) {
  int i, j;
  for (i = 2; i * i <= 10000000; i++)
    if (!isNotP[i])
      for (j = i * 2; j <= 10000000; j += i) isNotP[j] = 1;
  for (i = 3; i <= 10000000; i += 2)
    if (!isNotP[i]) p[len_p++] = i;
}
void pFactorize(int n) {
  int i;
  for (i = 0; p[i] * p[i] <= n; i++)
    if (n % p[i] == 0) {
      do {
        n /= p[i];
      } while (n % p[i] == 0);
      num_factor[p[i]]++;
    }
  if (n > 1) num_factor[n]++;
}
int main(void) {
  int i;
  int n, m;
  sieve();
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    pFactorize(x);
  }
  for (i = 3; i <= 10000000; i++) num_factor[i] += num_factor[i - 1];
  scanf("%d", &m);
  for (i = 0; i < m; i++) {
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%d\n", num_factor[r > 10000000 ? 10000000 : r] -
                       num_factor[l > 10000000 ? 10000000 : l - 1]);
  }
  return 0;
}
