#include <bits/stdc++.h>
using namespace std;
int N, M, cnt[10000010];
bool flag[10000010];
vector<int> prime, F;
void sieve() {
  F.push_back(0);
  for (long long i = 2; i <= 10000000; i++) {
    if (!flag[i]) {
      int sum = F.back() + cnt[i];
      prime.push_back(i);
      for (long long j = i * 2; j <= 10000000; j += i) {
        flag[j] = true;
        sum += cnt[j];
      }
      F.push_back(sum);
    }
  }
}
int query(int l, int r) {
  int left = lower_bound(prime.begin(), prime.end(), l) - prime.begin();
  int right = upper_bound(prime.begin(), prime.end(), r) - prime.begin();
  return F[right] - F[left];
}
int main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    int x;
    cin >> x;
    cnt[x]++;
  }
  sieve();
  cin >> M;
  for (int i = 0; i < M; i++) {
    int l, r;
    cin >> l >> r;
    cout << query(l, r) << endl;
  }
  return 0;
}
