#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int SIZE = 1e7 + 1;
int num[SIZE], cnt[SIZE], p[SIZE];
void prime_init() {
  for (int i = 2; i < SIZE; i++) {
    if (!p[i]) {
      for (int j = i; j < SIZE; j += i) {
        if (!p[j]) p[j] = i;
        cnt[i] += num[j];
      }
    }
  }
}
int main() {
  int(n);
  scanf("%d", &n);
  for (int i = 0; i < (n); ++i) {
    int(x);
    scanf("%d", &x);
    num[x]++;
  }
  prime_init();
  for (int i = (3); i < (SIZE); ++i) cnt[i] += cnt[i - 1];
  int(Q);
  scanf("%d", &Q);
  for (int k = 0; k < (Q); ++k) {
    int x, y;
    scanf("%d%d", &x, &y);
    if (x >= SIZE) {
      puts("0");
      continue;
    }
    if (y >= SIZE) y = SIZE - 1;
    printf("%d\n", cnt[y] - cnt[x - 1]);
  }
  return 0;
}
