// import chie template :) {{{
import std.stdio, std.algorithm, std.array, std.string, std.math, std.conv,
    std.range, std.container, std.bigint, std.ascii, std.typecons;

// }}}
// nep.scanner {{{
class Scanner
{
    import std.stdio : File, stdin;
    import std.conv : to;
    import std.array : split;
    import std.string : chomp;

    private File file;
    private char[][] str;
    private size_t idx;

    this(File file = stdin)
    {
        this.file = file;
        this.idx = 0;
    }

    private char[] next()
    {
        if (idx < str.length)
        {
            return str[idx++];
        }

        char[] s;
        while (s.length == 0)
        {
            s = file.readln.chomp.to!(char[]);
        }

        str = s.split;
        idx = 0;

        return str[idx++];
    }

    T next(T)()
    {
        return next.to!(T);
    }

    T[] nextArray(T)(size_t len)
    {
        T[] ret = new T[len];

        foreach (ref c; ret)
        {
            c = next!(T);
        }

        return ret;
    }

    void scan()()
    {
    }

    void scan(T, S...)(ref T x, ref S args)
    {
        x = next!(T);
        scan(args);
    }
}
// }}}

int[] getTable() {
    bool[] era = new bool[10010];
    era[2 .. $] = true;
    for (int i = 0; i * i < era.length; i++)
    {
        if (!era[i]) continue;
        for (int j = i + i; j < era.length; j += i)
        {
            era[j] = false;
        }
    }
    int[] res = new int[100010];
    foreach (i; 0 .. era.length)
    {
        if (era[i] && era[(i + 1) / 2])
        {
            res[i] = 1;
        }
    }
    foreach (i; 1 .. res.length) {
        res[i] += res[i - 1];
    }
    return res;
}

void main()
{
    static auto imos = getTable;
    auto cin = new Scanner;
    int q;
    cin.scan(q);
    foreach (i; 0 .. q) {
        int l, r;
        cin.scan(l, r);
        writeln(imos[r] - imos[l - 1]);
    }
}
