import std.stdio, std.algorithm, std.string, std.conv, std.array, std.range, std.math;
int readint() { return readln.chomp.to!int; }
int[] readints() { return readln.split.to!(int[]); }

bool isPrime(int x) {
    for (int i=2; i*i <= x; i++) if (x % i == 0) return false;
    return x != 1;
}

void main() {

    int[10^^5+5] a;
    foreach (i, v; a) {
        if (i & 1)
            a[i] = isPrime(i) & isPrime((i + 1) / 2);
    }
    foreach (i; 0..10^^5) a[i+1] += a[i];

    int q = readint();
    while (q--) {
        int l, r; readf("%d %d\n", &l, &r);
        writeln(a[r] - a[l-1]);
    }

    auto _ = readln(); // dbg
}