#include <bits/stdc++.h>
using namespace std;
int prime[1000000], ans[1000000] = {0}, sum[1000000] = {0};
bool not_prime[10000001] = {0};
inline int lowbit(const int& x) { return x & -x; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int prime_num = 0;
  for (int i = 2; i <= 10000000; ++i) {
    if (!not_prime[i]) prime[prime_num++] = i;
    for (int j = 0; j < prime_num && 1LL * i * prime[j] <= 10000000; ++j) {
      not_prime[i * prime[j]] = 1;
      if (!(i % prime[j])) break;
    }
  }
  prime[prime_num] = 10000001;
  int n, m, l, r, input;
  for (cin >> n; n; --n) {
    cin >> input;
    if (!not_prime[input])
      ++ans[lower_bound(prime, prime + prime_num, input) - prime];
    else
      for (int j = 0;; ++j) {
        if (!(input % prime[j])) {
          ++ans[j];
          do input /= prime[j];
          while (!(input % prime[j]));
        }
        if (prime[j] * prime[j] > input) {
          if (input != 1)
            ++ans[lower_bound(prime + (j + 1), prime + prime_num, input) -
                  prime];
          break;
        }
      }
  }
  ans[prime_num++] = 0;
  sum[0] = ans[0];
  for (int i = 1; i < prime_num; ++i) sum[i] = sum[i - 1] + ans[i];
  for (cin >> m; m; --m) {
    cin >> l >> r;
    r = min(r, 10000000);
    cout << (l <= r
                 ? sum[upper_bound(prime, prime + prime_num, r) - prime - 1] -
                       (l ? sum[lower_bound(prime, prime + prime_num, l) -
                                prime - 1]
                          : 0)
                 : 0)
         << '\n';
  }
  return 0;
}
