#include <bits/stdc++.h>
using namespace std;
int n, m, l, r, x;
int c[10000005], f[10000005];
bool vis[10000005];
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    c[x]++;
  }
  for (int i = 2; i < 10000005; i++)
    if (!vis[i])
      for (int j = i; j < 10000005; j += i) {
        vis[j] = 1;
        f[i] += c[j];
      }
  for (int i = 2; i < 10000005; i++) f[i] += f[i - 1];
  scanf("%d", &m);
  while (m--) {
    scanf("%d%d", &l, &r);
    if (l >= 10000005) l = 10000005 - 1;
    if (r >= 10000005) r = 10000005 - 1;
    printf("%d\n", f[r] - f[l - 1]);
  }
}
