#include <bits/stdc++.h>
using namespace std;
bool aray[10000009];
void sieve(long n) {
  long i, k, d;
  d = sqrt(n) + 1;
  for (i = 3; i < d; i = i + 2) {
    if (aray[i] != 1) {
      for (k = i * i; k <= n; k = k + 2 * i) aray[k] = 1;
    }
  }
}
long a[1000009], num[10000009], prime[670000], f[10000009];
long long r[670000], res;
int main() {
  ios_base::sync_with_stdio(0);
  long n, i, k, mx = 0, mn = 1000000000, m, x, y;
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    num[a[i]]++;
    if (a[i] > mx) mx = a[i];
  }
  sieve(mx + 1);
  long t = 2;
  prime[1] = 2;
  for (k = 3; k <= mx; k = k + 2) {
    if (aray[k] != 1) prime[t++] = k;
  }
  for (i = 1; i < t; i++) {
    x = prime[i];
    for (k = x; k <= mx; k = k + x) {
      if (num[k]) f[x] = f[x] + num[k];
    }
    r[i] = f[x] + r[i - 1];
  }
  cin >> m;
  long lp, up;
  for (i = 0; i < m; i++) {
    cin >> x >> y;
    lp = lower_bound(prime, prime + t, x) - prime;
    up = upper_bound(prime, prime + t, y) - prime;
    res = r[up - 1] - r[lp - 1];
    cout << res << endl;
  }
  return 0;
}
