#!/usr/bin/env python3
import sys
INF = float("inf")


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(Q: int, l: "List[int]", r: "List[int]"):

    # primes = eratosthenes_sieve(10**5)
    # prime_kai = [p for p in primes if (p+1)//2 in primes]

    prime_kai = [3, 5, 13, 37, 61, 73, 157, 193, 277, 313, 397, 421, 457, 541,
                 613, 661, 673, 733, 757, 877, 997, 1093, 1153, 1201, 1213,
                 1237, 1321, 1381, 1453, 1621, 1657, 1753, 1873, 1933, 1993,
                 2017, 2137, 2341, 2473, 2557, 2593, 2797, 2857, 2917, 3061,
                 3217, 3253, 3313, 3517, 3733, 4021, 4057, 4177, 4261, 4273,
                 4357, 4441, 4561, 4621, 4933, 5077, 5101, 5113, 5233, 5413,
                 5437, 5581, 5701, 6037, 6073, 6121, 6133, 6217, 6337, 6361,
                 6373, 6637, 6661, 6781, 6997, 7057, 7213, 7393, 7417, 7477,
                 7537, 7753, 7933, 8053, 8101, 8221, 8317, 8353, 8461, 8521,
                 8677, 8713, 8893, 9013, 9133, 9181, 9241, 9277, 9601, 9661,
                 9721, 9817, 9901, 9973, 10333, 10357, 10453, 10837, 10861,
                 10957, 11113, 11161, 11317, 11497, 11677, 11701, 12073, 12157,
                 12241, 12301, 12421, 12433, 12457, 12541, 12553, 12601, 12721,
                 12757, 12841, 12853, 13093, 13381, 13417, 13681, 13921, 13933,
                 14437, 14593, 14737, 14821, 15013, 15073, 15121, 15241, 15277,
                 15361, 15373, 15733, 15901, 16033, 16333, 16381, 16417, 16573,
                 16633, 16657, 16921, 17041, 17053, 17077, 17257, 17293, 17377,
                 17881, 18013, 18097, 18133, 18181, 18217, 18253, 18301, 18313,
                 18397, 18481, 18553, 18637, 18793, 19237, 19441, 19477, 19717,
                 19801, 19813, 19861, 20353, 20533, 20641, 20857, 21001, 21061,
                 21193, 21277, 21313, 21577, 21661, 21673, 21817, 22093, 22501,
                 22573, 22621, 22993, 23053, 23173, 23557, 23677, 23773, 23917,
                 24097, 24421, 24481, 24781, 24841, 25033, 25153, 25237, 25561,
                 25657, 25933, 26017, 26293, 26317, 26437, 26497, 26821, 26833,
                 26881, 26953, 27073, 27253, 27337, 27361, 27457, 27997, 28057,
                 28297, 28393, 28813, 28837, 28921, 29101, 29473, 29641, 30181,
                 30241, 30517, 30553, 30577, 30637, 30661, 30697, 30781, 30853,
                 31081, 31237, 31321, 31333, 31357, 31477, 31573, 31873, 31981,
                 32173, 32377, 32497, 32533, 32833, 33037, 33301, 33457, 33493,
                 33757, 33961, 34057, 34213, 34273, 34381, 34513, 34897, 34981,
                 35317, 35521, 35677, 35977, 36097, 36241, 36433, 36457, 36793,
                 36877, 36901, 36913, 37273, 37321, 37357, 37573, 37717, 37957,
                 38281, 38461, 38833, 38953, 38977, 39217, 39373, 39397, 39733,
                 40093, 40177, 40213, 40693, 40813, 41017, 41221, 41281, 41413,
                 41617, 41893, 42061, 42337, 42373, 42793, 42961, 43117, 43177,
                 43201, 43321, 43573, 43597, 43633, 43717, 44053, 44101, 44221,
                 44257, 44293, 44893, 45061, 45337, 45433, 45481, 45553, 45613,
                 45841, 46021, 46141, 46261, 46861, 46993, 47017, 47161, 47353,
                 47521, 47533, 47653, 47713, 47737, 47797, 47857, 48121, 48193,
                 48337, 48673, 48757, 48781, 49033, 49261, 49393, 49417, 49597,
                 49681, 49957, 50221, 50341, 50377, 50821, 50893, 51157, 51217,
                 51241, 51481, 51517, 51637, 52057, 52081, 52237, 52321, 52453,
                 52501, 52813, 52861, 52957, 53077, 53113, 53281, 53401, 53917,
                 54121, 54133, 54181, 54217, 54421, 54517, 54541, 54673, 54721,
                 54973, 55057, 55381, 55501, 55633, 55837, 55921, 55933, 56053,
                 56101, 56113, 56197, 56401, 56437, 56701, 56773, 56821, 56857,
                 56893, 57073, 57097, 57193, 57241, 57373, 57457, 57853, 58153,
                 58417, 58441, 58537, 58573, 58693, 59053, 59197, 59221, 59281,
                 59341, 59833, 60217, 60337, 60373, 60637, 60733, 60937, 61057,
                 61153, 61261, 61297, 61561, 61657, 61681, 61717, 61861, 62137,
                 62473, 62497, 62533, 62653, 62773, 63313, 63397, 63541, 63697,
                 63781, 63913, 64153, 64237, 64381, 64513, 64717, 65173, 65293,
                 65413, 65437, 65497, 65557, 65677, 65881, 66301, 66361, 66601,
                 66697, 66853, 66973, 67057, 67153, 67273, 67477, 67537, 67741,
                 67777, 67933, 67993, 68113, 68281, 68521, 68737, 69001, 69073,
                 69457, 69493, 69697, 69877, 70117, 70177, 70297, 70501, 70621,
                 70921, 70981, 71233, 71341, 71353, 71593, 71821, 72073, 72481,
                 72613, 72901, 72937, 73141, 73417, 73477, 73561, 73693, 74077,
                 74317, 74377, 74713, 75013, 75133, 75181, 75721, 75793, 75913,
                 76333, 76561, 76597, 76753, 77137, 77641, 78157, 78193, 78277,
                 78877, 78901, 79333, 79357, 79537, 79657, 79693, 79801, 79873,
                 80077, 80173, 80221, 80473, 80701, 80713, 80917, 81013, 81181,
                 81517, 81637, 81853, 82021, 82153, 82261, 82561, 82981, 83077,
                 83221, 83233, 83437, 83617, 83701, 83773, 84121, 84313, 84673,
                 84697, 84793, 84913, 85297, 85333, 85453, 85717, 85933, 86353,
                 86413, 87181, 87253, 87337, 87421, 87433, 87517, 87553, 87973,
                 88117, 88177, 88237, 88261, 88513, 88741, 88897, 88993, 89293,
                 89833, 89917, 90121, 91081, 91381, 91393, 91513, 91957, 92041,
                 92557, 92761, 92821, 92893, 92941, 93097, 93133, 93493, 93637,
                 93913, 94033, 94117, 94273, 94321, 94441, 94573, 94777, 94837,
                 94993, 95257, 95317, 95401, 95581, 95617, 95713, 95737, 96097,
                 96157, 96181, 96493, 96517, 96973, 97081, 97177, 97501, 97561,
                 97777, 97813, 98017, 98737, 98953, 99277, 99577, 99661, 99877]
    N = len(prime_kai)

    # print(prime_kai[:10])
    for ll, rr in zip(l, r):
        # print("({}, {})".format(ll, rr))
        left = -1
        right = N
        while right - left > 1:
            mid = left + (right - left) // 2
            if prime_kai[mid] < ll:
                left = mid
            else:
                right = mid
        hidari = right

        left = -1
        right = N
        while right - left > 1:
            mid = left + (right - left) // 2
            if prime_kai[mid] < rr+1:
                left = mid
            else:
                right = mid
        migi = right
        # print(hidari, migi)
        print(migi - hidari)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    Q = int(next(tokens))  # type: int
    l = [int()] * (Q)  # type: "List[int]"
    r = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        l[i] = int(next(tokens))
        r[i] = int(next(tokens))
    solve(Q, l, r)


if __name__ == '__main__':
    main()


Measured memory_bytes: 13624