using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Math;
using static System.Console;


class Program
{

    static void Main()
    {
        //3と4n+1のみ考える
        int[] likes = new int[100000+1];

        int prevIndex = 1;
        int count = 0;

        //n=3の場合OK
        prevIndex = 3;
        count++;


        //その他の場合
        for (int n = 0; n <= 25000; n++)
        {
            if(IsPrime(4 * n + 1) && IsPrime(2 * n + 1))
            {
                for (int i = prevIndex; i < 4 * n + 1; i++)
                {
                    likes[i] = count;
                }
                likes[4 * n + 1] = count++;
                prevIndex = 4 * n + 1;
            }
        }

        for (int i = prevIndex; i < likes.Length; i++)
        {
            likes[i] = count;
        }


        int Q = ReadInt();
        int[] ans = new int[Q];

        for (int i = 0; i < Q; i++)
        {
            int[] lr = ReadIntN();
            ans[i] = likes[lr[1]]-likes[lr[0]-1];
        }

        for (int i = 0; i < Q; i++)
        {
            WriteLine(ans[i]);
        }
        ReadLine();
    }

    static bool IsPrime(int n)
    {
        if (n == 1) return false;
        for (int i = 2; i <= (int)Sqrt(n); i++)
        {
            if (n % i == 0) return false;
        }
        return true;
    }

    #region Reader
    static string ReadStr()
    {
        return Console.ReadLine();
    }
    static string[] ReadStrN()
    {
        return Console.ReadLine().Split(' ');
    }
    static int ReadInt()
    {
        return Convert.ToInt32(Console.ReadLine());
    }
    static int[] ReadIntN()
    {
        return Console.ReadLine().Split(' ').Select(s => Convert.ToInt32(s)).ToArray();
    }
    static long ReadLong()
    {
        return Convert.ToInt64(Console.ReadLine());
    }
    static long[] ReadLongN()
    {
        return Console.ReadLine().Split(' ').Select(s => Convert.ToInt64(s)).ToArray();
    }
    static long[,] ReadLongMatrix(int r, int c)
    {
        var mat = new long[r, c];
        for (int i = 0; i < r; ++i)
        {
            var x = ReadLongN();
            for (int j = 0; j < c; ++j)
            {
                mat[i, j] = x[j];
            }
        }
        return mat;
    }
    static Tuple<string, string>[] ReadTupleStr(int n)
    {
        List<Tuple<string, string>> list = new List<Tuple<string, string>>();
        for (int i = 0; i < n; ++i)
        {
            var ab = ReadStrN();
            list.Add(new Tuple<string, string>(ab[0], ab[1]));
        }
        return list.ToArray();
    }
    static Tuple<long, long>[] ReadTupleLong(int n)
    {
        List<Tuple<long, long>> list = new List<Tuple<long, long>>();
        for (int i = 0; i < n; ++i)
        {
            var ab = ReadLongN();
            list.Add(new Tuple<long, long>(ab[0], ab[1]));
        }
        return list.ToArray();
    }
    static Tuple<int, int>[] ReadTupleInt(int n)
    {
        List<Tuple<int, int>> list = new List<Tuple<int, int>>();
        for (int i = 0; i < n; ++i)
        {
            var ab = ReadIntN();
            list.Add(new Tuple<int, int>(ab[0], ab[1]));
        }
        return list.ToArray();
    }
    static Tuple<double, double>[] ReadTupleDouble(int n)
    {
        List<Tuple<double, double>> list = new List<Tuple<double, double>>();
        for (int i = 0; i < n; ++i)
        {
            var ab = ReadLongN();
            list.Add(new Tuple<double, double>(ab[0], ab[1]));
        }
        return list.ToArray();
    }
    static Dictionary<int, HashSet<int>> ReadAdjacencyList(int N, int M)
    {
        Dictionary<int, HashSet<int>> dict = new Dictionary<int, HashSet<int>>();
        for (int i = 0; i <= N; ++i)
        {
            dict.Add(i, new HashSet<int>());
        }
        for (int i = 0; i < M; ++i)
        {
            var ab = ReadIntN();
            dict[ab[0]].Add(ab[1]);
            dict[ab[1]].Add(ab[0]);
        }
        return dict;
    }
    #endregion
}


Measured memory_bytes: 18360