#include <bits/stdc++.h>
using namespace std;
vector<long long> v(10000008, 0);
int main() {
  long long n;
  scanf("%lld", &n);
  v[0] = 1, v[1] = 1;
  for (long long i = 2; i * i < 10000008; i++) {
    if (v[i] == 0) {
      long long p = i;
      while (p * i < 10000008) {
        v[p * i] = 1;
        p++;
      }
    }
  }
  vector<long long> prime;
  for (long long i = 0; i < 10000008; i++) {
    if (v[i] == 0) prime.push_back(i);
    v[i] = 0;
  }
  long long p;
  for (long long i = 0; i < n; i++) {
    scanf("%lld", &p);
    v[p]++;
  }
  map<long long, long long> mp;
  for (auto it : prime) {
    long long p = it;
    long long q = 1;
    long long count = 0;
    while (p * q < 10000008) {
      count += v[p * q];
      q++;
    }
    if (count > 0) {
      mp[it] = count;
    }
  }
  for (long long i = 0; i < 10000008; i++) {
    v[i] = 0;
  }
  for (auto it : mp) {
    v[it.first] = it.second;
  }
  for (long long i = 1; i < 10000008; i++) v[i] += v[i - 1];
  long long t;
  cin >> t;
  long long a, b;
  while (t--) {
    scanf("%lld %lld", &a, &b);
    if (b > 10000000) b = 10000000;
    if (a > 10000000) a = 10000000;
    printf("%lld\n", v[b] - v[a - 1]);
  }
  return 0;
}
