#include <bits/stdc++.h>
using namespace std;
int i, j, fx[10000002], a[1000001], b[50001], c[50001], f[10000002], n, m, x, y,
    k, mx, s[10000002];
bool t;
int main() {
  fx[1] = 5;
  for (i = 1; i <= 10000001; i++) {
    if (fx[i] == 0)
      for (j = i; j <= 10000001; j += i) fx[j] = i;
  }
  cin >> n;
  for (i = 1; i <= n; i++) scanf("%d", &a[i]);
  cin >> m;
  for (i = 1; i <= m; i++) {
    scanf("%d%d", &b[i], &c[i]);
    mx = max(mx, c[i]);
  }
  for (i = 1; i <= n; i++) {
    x = -1;
    k = a[i];
    while (k > 1) {
      if (x != fx[k]) {
        y = fx[k];
        f[y]++;
      }
      x = fx[k];
      k /= y;
    }
  }
  s[1] = f[1];
  for (i = 2; i <= 10000001; i++) s[i] = s[i - 1] + f[i];
  for (i = 1; i <= m; i++) {
    x = b[i];
    y = c[i];
    if (y > 10000000 && x > 10000000)
      printf("0\n");
    else if (y > 10000000)
      printf("%d\n", (s[10000001] - s[x - 1]));
    else
      printf("%d\n", (s[y] - s[x - 1]));
  }
}
