# D - 2017-like Number

# # n以下の全ての素数のセットを返す関数
# def prime_set(n):
#     primes = set(range(2, n+1))
#     for i in range(2, int(n**0.5) + 1):
#         primes.difference_update(range(i*2, n+1, i))
#     return primes

# p_set = prime_set(10**5)
# like_number = []

# for i in range(1, 10**5, 2):
#     if i in p_set and (i+1)//2 in p_set:
#         like_number.append(i)

like_number = [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]

import sys, bisect

Q = int(sys.stdin.buffer.readline())
for _ in range(Q):
    l, r = map(int, sys.stdin.buffer.readline().split())
    print(bisect.bisect_right(like_number, r) - bisect.bisect_left(like_number, l))

Measured memory_bytes: 4272