import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 1_000_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Clue = Tuple!(long, "x", long, "y", long, "h");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

long cnt;

void main()
{
    auto ary = new long[](MAX);
    auto is_prime = new bool[](MAX);
    is_prime[] = true;
    is_prime[0] = is_prime[1] = false;
    foreach (i; iota(MAX))
    {
        if (!is_prime[i])
            continue;

        foreach (j; iota(0, MAX, i))
        {
            is_prime[j] = false;
        }
        is_prime[i] = true;
    }
    foreach (i; iota(1, MAX))
        ary[i] = ary[i - 1] + (is_prime[i] && is_prime[(i + 1) / 2] ? 1 : 0);
    auto q = lread();
    foreach (i; iota(q))
    {
        long l, r;
        scan(l, r);
        writeln(ary[r] - ary[l - 1]);
    }
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}
