using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.ComponentModel;

class Scanner
{
    private readonly char Separator = ' ';
    private int Index = 0;
    private string[] Line = new string[0];

    private T Convert<T>(string s)
    {
        return (T)TypeDescriptor.GetConverter(typeof(T)).ConvertFromString(s);
    }

    public string Next()
    {
        if (Index >= Line.Length)
        {
            Line = Console.ReadLine().Split(Separator);
            Index = 0;
        }
        var ret = Line[Index];
        Index++;
        return ret;
    }

    public T Next<T>()
    {
        return Convert<T>(Next());
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public string[] StringArray()
    {
        Line = Console.ReadLine().Split(Separator);
        Index = Line.Length;
        return Line;
    }

    public T[] Array<T>()
    {
        var l = StringArray();
        var res = new T[l.Length];
        for (int i = 0; i < l.Length; i++)
        {
            res[i] = Convert<T>(l[i]);
        }
        return res;
    }

    public int[] IntArray()
    {
        var l = StringArray();
        var res = new int[l.Length];
        for (int i = 0; i < l.Length; i++)
        {
            res[i] = int.Parse(l[i]);
        }
        return res;
    }

    public long[] LongArray()
    {
        var l = StringArray();
        var res = new long[l.Length];
        for (int i = 0; i < l.Length; i++)
        {
            res[i] = long.Parse(l[i]);
        }
        return res;
    }
}

class Program
{
    private int Max = 100000;
    private long[] Sum;

    private int Q;
    private int[] L, R;
    private void Scan()
    {
        var sc = new Scanner();
        Q = sc.NextInt();
        L = new int[Q];
        R = new int[Q];
        for (int i = 0; i < Q; i++)
        {
            L[i] = sc.NextInt();
            R[i] = sc.NextInt();
        }
    }

    private void Calc()
    {
        var isNotPrime = new bool[Max + 1];
        isNotPrime[0] = true;
        isNotPrime[1] = true;
        for (int i = 2; i * i <= Max; i++)
        {
            if (!isNotPrime[i])
            {
                for (int j = i + i; j <= Max; j += i)
                {
                    isNotPrime[j] = true;
                }
            }
        }
        bool[] A = new bool[Max + 1];
        for (int i = 0; i <= Max; i++)
        {
            A[i] = (!isNotPrime[i]) && (!isNotPrime[(i + 1) / 2]);
        }
        Sum = new long[Max + 1];
        for (int i = 1; i <= Max; i++)
        {
            Sum[i] = Sum[i - 1];
            if (A[i])
            {
                Sum[i]++;
            }
        }
    }


    public void Solve()
    {
        Scan();
        Calc();
        var sb = new StringBuilder();
        for (int i = 0; i < Q; i++)
        {
            sb.AppendLine((Sum[R[i]] - Sum[L[i] - 1]).ToString());
        }
        Console.Write(sb.ToString());
    }


    static void Main(string[] args)
    {
        new Program().Solve();
    }
}

Measured memory_bytes: 18756