import std.stdio;
import std.string;
import std.conv;
import std.algorithm;

void inputLine(A...)(ref A a) {
    string[] line = readln.chomp.split;
    if (a.length != line.length) {
        throw new Exception("not equal number of input elements and number of variable elements.");
    }
    foreach (int i, ref e; a) {
        e = line[i].to!(A[i]);
        // e = line[i].to!(typeof(e));
    }
}

bool[100010] p;

void calcPrime() {
    p[] = true;
    p[0] = p[1] = false;
    for (int i = 4; i < 100; i++) {
        for (int j = 2; j * j <= i; j++) {
            if (p[j]) {
                p[i] &= i % j ? true : false;
            }
        }
    }
}

void main() {
    int Q = readln.chomp.to!(int);
    calcPrime();

    int[100010] hoge;
    for (int i = 1; i < 100010; i++) {
        hoge[i] = hoge[i - 1] + (p[i] & p[(i + 1) / 2]);
    }

    for (int i = 0; i < Q; i++) {
        int l, r;
        inputLine(l, r);
        writeln(hoge[r] - hoge[l - 1]);
    }
}
