#include <bits/stdc++.h>
bool prime[10000000 + 1] = {false};
int count[10000000 + 1] = {0};
int F[10000000 + 1] = {0};
void makePrime() {
  int limit = sqrt((double)10000000);
  for (int i = 0; i <= 10000000; i++) prime[i] = true;
  prime[0] = prime[1] = false;
  for (int i = 2; i <= limit; i++) {
    if (prime[i]) {
      for (int k = 10000000 / i, j = i * k; k >= i; k--, j -= i) {
        if (prime[k]) prime[j] = false;
      }
    }
  }
}
void compute() {
  for (int i = 2; i <= 10000000; i++) {
    if (prime[i]) {
      for (int j = i; j <= 10000000; j += i) F[i] += count[j];
    }
  }
  for (int i = 1; i <= 10000000; i++) F[i] += F[i - 1];
}
int main() {
  makePrime();
  int n, m;
  while (scanf("%d", &n) == 1) {
    for (int i = 0; i < n; i++) {
      int tmp;
      scanf("%d", &tmp);
      count[tmp]++;
    }
    compute();
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
      int L, R;
      scanf("%d%d", &L, &R);
      if (R > 10000000) R = 10000000;
      if (L > 10000000)
        printf("%d\n", 0);
      else
        printf("%d\n", F[R] - F[L - 1]);
    }
  }
  return 0;
}
