#include <bits/stdc++.h>
using namespace std;
int n, m;
long long int tmp;
long long int cnt[10000007 + 5];
bool pri[10000007 + 5];
long long int p[10000007 + 5];
long long int pre[10000007 + 9];
void sv() {
  memset(pri, false, sizeof(false));
  for (int i = 2; i < 10000007; i++) {
    if (pri[i] == false) {
      for (int j = i; j < 10000007; j += i) {
        p[i] += cnt[j];
        pri[j] = true;
      }
    }
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%lld", &tmp);
    cnt[tmp]++;
  }
  sv();
  for (int i = 1; i <= 10000007; i++) {
    pre[i] = pre[i - 1] + p[i];
  }
  cin >> m;
  while (m--) {
    int u, v;
    scanf("%d%d", &u, &v);
    u = min(10000007 - 5, u);
    v = min(10000007 - 5, v);
    long long int ans;
    ans = pre[v] - pre[u - 1];
    printf("%lld\n", ans);
  }
  return 0;
}
