import bisect

from operator import itemgetter



Q = int(eval(input()))

lr = [list(map(int, input().split())) for _ in range(Q)]



rmax = max(lr, key=itemgetter(1))[1]

primes = list(range(rmax+1))

primes [1] = 0



for i in range(2, int(rmax**0.5)+ 2):

    for j in range(2 * i, rmax+1, i):

        primes[j] = 0

primes = [prime for prime in primes[:] if prime!=0]



lst2017 = [x for x in primes if x != 2 and (x+1)//2 in primes]



for l, r in lr:

    nr = bisect.bisect_right(lst2017, r)

    nl = bisect.bisect_left(lst2017, l)

    print((nr - nl))
import bisect

from operator import itemgetter



Q = int(eval(input()))

lr = [list(map(int, input().split())) for _ in range(Q)]



rmax = max(lr, key=itemgetter(1))[1]

primes = list(range(rmax+1))

primes [1] = 0



for i in range(2, int(rmax**0.5)+ 2):

    for j in range(2 * i, rmax+1, i):

        primes[j] = 0

primess = [prime for prime in primes[:] if prime!=0]

lst2017 = [x for x in primess if primes[(x+1)//2] != 0]



for l, r in lr:

    nr = bisect.bisect_right(lst2017, r)

    nl = bisect.bisect_left(lst2017, l)

    print((nr - nl))
import bisect
from operator import itemgetter

Q = int(eval(input()))
lr = [list(map(int, input().split())) for _ in range(Q)]
rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax + 1))
primes[1] = 0
for i in range(2, int(rmax**0.5) + 2):
    for j in range(2 * i, rmax + 1, i):
        primes[j] = 0
primes = [prime for prime in primes[:] if prime != 0]
lst2017 = [x for x in primes if x != 2 and (x + 1) // 2 in primes]
for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print((nr - nl))

import bisect
from operator import itemgetter

Q = int(eval(input()))
lr = [list(map(int, input().split())) for _ in range(Q)]
rmax = max(lr, key=itemgetter(1))[1]
primes = list(range(rmax + 1))
primes[1] = 0
for i in range(2, int(rmax**0.5) + 2):
    for j in range(2 * i, rmax + 1, i):
        primes[j] = 0
primess = [prime for prime in primes[:] if prime != 0]
lst2017 = [x for x in primess if primes[(x + 1) // 2] != 0]
for l, r in lr:
    nr = bisect.bisect_right(lst2017, r)
    nl = bisect.bisect_left(lst2017, l)
    print((nr - nl))

-primes = [prime for prime in primes[:] if prime != 0] -lst2017 = [x for x in primes if x != 2 and (x + 1) // 2 in primes] +primess = [prime for prime in primes[:] if prime != 0] +lst2017 = [x for x in primess if primes[(x + 1) // 2] != 0]