#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int occur[(int)1e7 + 1];
int n, m;
int sum[(int)1e7 + 1];
int vis[(int)1e7 + 1];
int main() {
  ios::sync_with_stdio(false);
  memset(occur, 0, sizeof(occur));
  memset(vis, 0, sizeof(vis));
  memset(sum, 0, sizeof(sum));
  cin >> n;
  for (int i = 2; i <= 1e7; ++i) {
    if (vis[i]) continue;
    for (int j = i; j <= 1e7; j += i) {
      vis[j] = i;
    }
  }
  for (int i = 1; i <= n; ++i) {
    int temp;
    cin >> temp;
    while (temp > 1) {
      int p = vis[temp];
      sum[p] += 1;
      while (temp % p == 0) {
        temp /= p;
      }
    }
  }
  for (int i = 2; i <= 1e7; ++i) sum[i] += sum[i - 1];
  cin >> m;
  for (int i = 1; i <= m; ++i) {
    int l, r;
    cin >> l >> r;
    int upper, lower;
    if (r > 1e7)
      upper = sum[(int)1e7];
    else
      upper = sum[r];
    if (l > 1e7)
      lower = sum[(int)1e7];
    else
      lower = sum[l - 1];
    cout << upper - lower << '\n';
  }
}
