#include <bits/stdc++.h>
using namespace std;
template <class T>
void print_array(T a[], int size) {
  for (int i = 0; i < size; i++) cout << a[i] << " ";
  cout << endl;
}
template <class T>
void print_array_v(T &a) {
  int size = a.size();
  for (int i = 0; i < size; i++) cout << a[i] << " ";
  cout << endl;
}
const int MAXN = 1e7 + 10;
int cnt[MAXN] = {0};
int ps[MAXN] = {0};
int tot[MAXN] = {0};
int main() {
  int n, num;
  cin >> n;
  for (int i = 0; i < n; i++) {
    scanf("%d", &num);
    cnt[num]++;
  }
  ps[0] = ps[1] = 1;
  for (int i = 2; i < MAXN; i++) {
    if (ps[i]) continue;
    for (int j = i; j < MAXN; j += i) {
      ps[j] = 1;
      tot[i] += cnt[j];
    }
  }
  for (int i = 1; i < MAXN; i++) tot[i] += tot[i - 1];
  int m;
  cin >> m;
  int l, r;
  for (int i = 0; i < m; i++) {
    scanf("%d", &l);
    scanf("%d", &r);
    r = min(MAXN - 1, r);
    l = min(l, r);
    printf("%d\n", tot[r] - tot[l - 1]);
  }
  return 0;
}
