#include <bits/stdc++.h>
using namespace std;
int prime[10000002], ar[10000002], k = 0, store[10000002], ar2[10000002];
void mark(int n) {
  int idx = 0, f;
  while (ar[idx] * ar[idx] <= n) {
    f = 0;
    while (n % ar[idx] == 0) {
      n = n / ar[idx];
      f = 1;
    }
    if (f) {
      store[ar[idx]] += 1;
    }
    idx++;
  }
  if (prime[n] == 0) store[n] += 1;
}
void gen() {
  int i, j;
  for (i = 4; i <= 10000002; i += 2) prime[i] = 1;
  for (i = 3; i * i <= 10000002; i += 2) {
    if (prime[i] == 0) {
      for (j = i * i; j < 10000002; j = j + 2 * i) prime[j] = 1;
    }
  }
  for (i = 2; i <= 10000002; i++) {
    if (prime[i] == 0) ar[k++] = i;
  }
}
int main() {
  int n;
  scanf("%d", &n);
  int inp[n + 1];
  for (int i = 1; i <= n; i++) {
    scanf("%d", &inp[i]);
  }
  gen();
  for (int i = 1; i <= n; i++) {
    mark(inp[i]);
  }
  for (int i = 0; i < 10000002; i++) {
    if (!i)
      ar2[i] = store[i];
    else
      ar2[i] = ar2[i - 1] + store[i];
  }
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    if (l > 10000002) {
      printf("0\n");
      continue;
    }
    if (r > 10000002) {
      r = 10000002 - 1;
    }
    printf("%d\n", max(ar2[r] - ar2[l - 1], 0));
  }
  return 0;
}
