#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:500000000")
using namespace std;
int p[10000009];
int main() {
  int i, j;
  for (i = 2; i * i < 10000009; i++)
    if (p[i] == 0)
      for (j = i * i; j < 10000009; j += i) p[j] = i;
  for (i = 0; i < 10000009; i++)
    if (p[i] == 0) p[i] = i;
  vector<int> L;
  int n, q, x;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &x);
    while (x > 1) {
      int c = p[x];
      while (x % c == 0) x /= c;
      L.push_back(c);
    }
  }
  sort(L.begin(), L.end());
  scanf("%d", &q);
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    printf("%d\n", upper_bound(L.begin(), L.end(), r) -
                       lower_bound(L.begin(), L.end(), l));
  }
}
