#include <bits/stdc++.h>
using namespace std;
const int N = 10000002;
int sum[N + 5];
int vis[N + 5];
int num[N + 5];
int a[N + 5];
void init() {
  memset(vis, 0, sizeof(vis));
  memset(sum, 0, sizeof(sum));
  memset(num, 0, sizeof(num));
  for (int i = 2; i <= N; i++)
    if (!vis[i]) {
      for (int j = i; j <= N; j += i) {
        vis[j] = 1;
        num[i] += a[j];
      }
    }
  for (int i = 1; i <= N; i++) sum[i] = sum[i - 1] + num[i];
}
int main() {
  int n, x, l, r;
  cin >> n;
  memset(a, 0, sizeof(a));
  for (int i = 0; i < n; ++i) {
    cin >> x;
    a[x]++;
  }
  init();
  int m;
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> l >> r;
    l = min(N, l);
    r = min(N, r);
    cout << sum[r] - sum[l - 1] << endl;
  }
}
