#include <bits/stdc++.h>
using namespace std;
int sieve[10000002], h[10000002], cnt[10000002];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  for (int i = 4; i < 10000002; i += 2) sieve[i] = 1;
  for (int i = 3; i * i <= 10000002; i += 2)
    if (!sieve[i])
      for (int j = i * i; j < 10000002; j += i + i) sieve[j] = 1;
  int n, x;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> x, h[x]++;
  for (int i = 2; i < 10000002; i++) {
    if (!sieve[i]) {
      for (int j = i; j < 10000002; j += i) cnt[i] += h[j];
    }
  }
  for (int i = 1; i < 10000002; i++) cnt[i] += cnt[i - 1];
  int q;
  cin >> q;
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << cnt[min(r, 10000002 - 1)] - cnt[min(l - 1, 10000002 - 1)] << endl;
  }
}
