void main()
{
    auto sieve = Sieve!long(10^^5);
    long[] dp = new long[10^^5+1];
    foreach (i; 1 .. 10^^5+1)
    {
        dp[i] = dp[i-1];
        if (sieve.isPrime(i) && sieve.isPrime((i+1)/2))
        {
            ++dp[i];
        }
    }

    long q = readln.chomp.to!long;
    foreach (i; 0 .. q)
    {
        long[] tmp = readln.split.to!(long[]);
        long l = tmp[0] - 1, r = tmp[1];
        writeln(dp[r] - dp[l]);
    }
}

struct Sieve(T)
{
    bool[] flags;

    this(T limit)
    {
        flags = sieve(limit);
    }

    bool[] sieve(T limit)
    {
        long len = (limit - 1) / 2;
        bool[] result = new bool[len];
        result[] = true;
        foreach (i; 0 .. len)
        {
            if (!result[i]) continue;

            long prime = 3 + 2 * i;
            foreach (j; iota(prime+i, len, prime))
            {
                result[j] = false;
            }
        }
        return result;
    }

    size_t length() @property
    {
        return flags.length;
    }

    bool isPrime(T x)
    {
        if (x < 2)
        {
            return false;
        }
        else if (x == 2)
        {
            return true;
        }
        else if (x % 2 == 0)
        {
            return false;
        }
        else
        {
            return flags[(x-3)/2];
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;