import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

int[] sieve(int n) {
    assert(n > 1);
    auto t = new bool[n + 1];
    int[] primes = [2];
    for (int i = 3; i < t.length; i += 2) {
        if (!t[i]) {
            primes ~= i;
            for (int j = i + i; j < t.length; j += i)
                t[j] = true;
        }
    }
    return primes;
}

void main() {
    int n = 10 ^^ 5;
    auto pmap = new bool[n + 1];
    foreach (p; sieve(n)) pmap[p] = true;

    bool isLike(int n) {
        if (n % 2 == 0) return false;
        if (pmap[n] && pmap[(n + 1) / 2]) return true;
        return false;
    }

    auto t = new int[n + 1];
    for (int i = 3; i <= n; i++) {
        t[i] = t[i - 1] + (isLike(i) ? 1 : 0);
    }

    int q = readint;
    for (int i = 0; i < q; i++) {
        auto lr = readints;
        int l = lr[0];
        int r = lr[1];

        writeln(t[r] - t[l - 1]);
    }
}
