#include <bits/stdc++.h>
using namespace std;
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename A, typename B>
istream& operator>>(istream& input, pair<A, B>& x) {
  input >> x.first >> x.second;
  return input;
}
template <typename A>
istream& operator>>(istream& input, vector<A>& x) {
  for (auto& i : x) input >> i;
  return input;
}
int cnt[10000005], sieve[10000005];
void solve() {
  for (int i = 2; i * i <= 10000000; i++)
    if (!sieve[i])
      for (int j = i * i; j <= 10000000; j += i) sieve[j] = i;
  for (int i = 2; i < 10000001; i++)
    if (!sieve[i]) sieve[i] = i;
  int n;
  cin >> n;
  while (n--) {
    int x;
    cin >> x;
    while (x > 1) {
      int p = sieve[x];
      cnt[p]++;
      while (x % p == 0) x /= p;
    }
  }
  for (int i = 1; i < 10000001; i++) cnt[i] += cnt[i - 1];
  int m;
  cin >> m;
  while (m--) {
    int l, r;
    cin >> l >> r;
    if (l > 10000000) {
      cout << 0 << '\n';
      continue;
    }
    r = min(r, 10000000);
    cout << cnt[r] - cnt[l - 1] << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
