#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
unordered_map<int, int> mp;
int n, q;
int d[((int)1e7 + 5) + 1000];
int pre[((int)1e7 + 5) + 1000];
bool prime[((int)1e7 + 5) + 1000];
vector<int> primes;
unordered_map<int, int> ans;
void findprime() {
  for (int i = 2; i * i < ((int)1e7 + 5); ++i)
    if (prime[i] == 0) {
      primes.push_back(i);
      for (int j = 2 * i; j * j < ((int)1e7 + 5); j += i) prime[j] = 1;
    }
}
void setup(clock_t tm) {
  findprime();
  for (auto i : mp) {
    int num = i.first;
    int times = i.second;
    for (auto pr : primes) {
      if (pr * pr > num) break;
      if (num % pr == 0) {
        num /= pr;
        ans[pr] += times;
        while (num % pr == 0) num /= pr;
      }
    }
    if (num > 1) ans[num] += times;
  }
  pre[0] = 0;
  pre[1] = 0;
  for (int i = 2; i < ((int)1e7 + 5); ++i) {
    pre[i] = pre[i - 1];
    if (ans.count(i) > 0) pre[i] += ans[i];
  }
}
int query(int a, int b) {
  int push_back;
  if (b > 1e7)
    push_back = pre[int(1e7)];
  else
    push_back = pre[b];
  int pa;
  if (a - 1 > 1e7)
    pa = pre[int(1e7)];
  else
    pa = pre[a - 1];
  return push_back - pa;
}
int main() {
  clock_t tm = clock();
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &d[i]);
    mp[d[i]]++;
  }
  setup(tm);
  cin >> q;
  while (q--) {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", query(a, b));
  }
  return 0;
}
