#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1000 * 1000;
const int MaxNum = 10 * 1000 * 1000;
int a[MaxN];
int hMany[MaxNum + 1];
long long ans[MaxNum + 1];
int lp[MaxNum + 1];
int pr[MaxNum];
int szPr = 0;
void getPrimes(int pos, int x) {
  for (int i = 0; i < szPr; i++) {
    if (pr[i] * pr[i] > x) break;
    if (x % pr[i] == 0) {
      while (x % pr[i] == 0) x /= pr[i];
      hMany[pr[i]]++;
    }
  }
  if (x != 0) hMany[x]++;
}
int main() {
  for (int i = 2; i <= MaxNum; i++) {
    if (lp[i] == 0) {
      lp[i] = i;
      pr[szPr++] = i;
    }
    for (int j = 0; j < szPr && pr[j] <= lp[i] && i * pr[j] <= MaxNum; j++)
      lp[i * pr[j]] = pr[j];
  }
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    getPrimes(i, a[i]);
  }
  for (int i = 1; i <= MaxNum; i++) ans[i] = ans[i - 1] + hMany[i];
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    if (l > MaxNum)
      printf("0\n");
    else {
      r = min(r, MaxNum);
      printf("%lld\n", ans[r] - ans[l - 1]);
    }
  }
}
