#include <bits/stdc++.h>
using namespace std;
const long long sz = 10000001;
bool vis[sz];
int cs[sz], a[sz], n, m;
void run() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
int main() {
  run();
  cin >> n;
  int x;
  for (int i = 0; i < n; i++) {
    cin >> x;
    a[x]++;
  }
  for (int i = 2; i < sz; i++)
    if (!vis[i])
      for (int j = i; j < sz; j += i) {
        vis[j] = 1;
        if (a[j]) cs[i] += a[j];
      }
  for (int i = 3; i < sz; i++) cs[i] = cs[i] + cs[i - 1];
  cin >> m;
  while (m--) {
    long long l, r;
    cin >> l >> r;
    r = min(r, sz - 1);
    l = min(l, sz - 1);
    cout << cs[r] - cs[l - 1] << endl;
  }
  return 0;
}
