#include <bits/stdc++.h>
using namespace std;
long long prime[(long long)1e7 + 9 + 1];
long long freq[(long long)1e7 + 9 + 1];
long long sieve[(long long)1e7 + 9 + 1];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n;
  cin >> n;
  for (long long i = 0; i < n; i++) {
    long long first;
    cin >> first;
    freq[first]++;
  }
  long long mini = 2;
  long long maxi = 2;
  for (long long i = 2; i <= (long long)1e7 + 9; i++)
    if (!sieve[i]) {
      maxi = max(maxi, i);
      for (long long j = i; j <= (long long)1e7 + 9; j += i)
        prime[i] += freq[j], sieve[j] = 1;
    }
  for (long long i = 3; i <= (long long)1e7 + 9; i++) prime[i] += prime[i - 1];
  long long m;
  cin >> m;
  while (m--) {
    long long l, r;
    cin >> l >> r;
    if (r < mini || maxi < l) {
      cout << "0\n";
      continue;
    }
    r = min(maxi, r);
    l = max(l, mini);
    cout << prime[r] - prime[l - 1] << '\n';
  }
  return 0;
}
