#include <bits/stdc++.h>   using namespace std;   const int N = 10000010;   int p[N], num, last[N];   bool flag[N];   int cnt[N], n, m;   void make_prime() {     for (int i = 2; i < N; ++i)       if (!flag[i]) {         p[num++] = i;         last[i] = i;         for (int j = i + i; j < N; j += i) flag[j] = true, last[j] = i;       }   }   int main() {     make_prime();     scanf( %d , &n);     for (int i = 0, x; i < n; ++i) {       scanf( %d , &x);       int s = -1;       while (x != 1) {         if (last[x] != s) cnt[last[x]]++;         s = last[x];         x /= last[x];       }     }     for (int i = 1; i < N; ++i) cnt[i] += cnt[i - 1];     scanf( %d , &m);     for (int i = 0, x, y; i < m; ++i) {       scanf( %d %d , &x, &y);       if (x >= N)         puts( 0 );       else {         y = min(y, N - 1);         printf( %d n , cnt[y] - cnt[x - 1]);       }     }     return 0;   }   