#include <bits/stdc++.h>using namespace std;
int n, t, f[100005], l, r, x;
bool p[10000007];
void snt () {
memset(p, true, sizeof(p));
p[0] = p[1] = false;
for(int i = 2; i * i <= 10000007; i ++) {
if(p[i]) {
for(int j = i * i; j <= 10000007; j += i) p[j] = false; } }}
bool check(int a) {
    int c = 0, b[10], d = 0, s = 0;
    if(p[a]) {
        for(int i = 0; i <= 9; i ++) {
            if(p[a * 10 + i]) {
                c = 1;
                break;            }        }
        if(c == 0) return 0;
        while(a > 0) {
            b[++ d] = a % 10;            a /= 10;        }
        for(int i = d; i > 1; i --) {
            s = s * 10 + b[i];
            if(!p[s]) return 0;        }
        return 1;    }
    return 0;} 
int main() {
    snt();
    cin >> n;    for(int i = 1; i <= n; i ++) {
        cin >> x;
        f[i] = f[i - 1];
        if(check(x)) f[i] ++;    }
    cin >> t;    while(t --) {
        cin >> l >> r;
        cout << f[r] - f[l - 1] << '\n';    }
    return 0;}