# Original solution
from itertools import accumulate


def get_primes_til(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n ** .5) + 1):
        if is_prime[i]:
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
    return {i for i in range(2, n + 1) if is_prime[i]}


N_MAX = 10 ** 5
primes = get_primes_til(N_MAX)
is_2017_like = list(accumulate([i in primes and (i + 1) // 2 in primes for i in range(N_MAX + 1)]))
for _ in range(int(eval(input()))):
    l, r = list(map(int, input().split()))
    print((is_2017_like[r] - is_2017_like[l - 1]))


# Optimized solution
from itertools import accumulate


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