Q = int(eval(input()))



from functools import lru_cache

@lru_cache(maxsize=None)

def is_prime(n: int):

    if n == 2:

        return True

    if n == 1 or n % 2 == 0:

        return False

    for p in range(3, int(n**0.5)+1, 2):

        if n % p == 0:

            return False

    return True



like_2017s = []

for i in range(3, 10**5, 2):

    if is_prime(i) and is_prime((i+1)//2):

        like_2017s.append(i)



from bisect import bisect_left, bisect_right

for _ in range(Q):

    l, r = list(map(int, input().split()))

    li = bisect_left(like_2017s, l)

    ri = bisect_right(like_2017s, r)

    print((ri-li))
Q = int(eval(input()))



import math

def sieve_of_erastosthenes(num):

    input_list = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)]

    input_list[0] = input_list[1] = False

    input_list[2] = input_list[3] = input_list[5] = True

    sqrt = math.sqrt(num)

    for serial in range(3, num, 2):

        if serial >= sqrt:

            return input_list

        for s in range(serial ** 2, num, serial): 

            input_list[s] = False



primes = sieve_of_erastosthenes(10**5)

likes = []

for i in range(3, 10**5, 2):

    if primes[i] and primes[(i+1)//2]:

        likes.append(i)



from bisect import bisect_left, bisect_right



for _ in range(Q):

    l, r = list(map(int, input().split()))

    print((bisect_right(likes, r) - bisect_left(likes, l)))
Q = int(eval(input()))
from functools import lru_cache


@lru_cache(maxsize=None)
def is_prime(n: int):
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for p in range(3, int(n**0.5) + 1, 2):
        if n % p == 0:
            return False
    return True


like_2017s = []
for i in range(3, 10**5, 2):
    if is_prime(i) and is_prime((i + 1) // 2):
        like_2017s.append(i)
from bisect import bisect_left, bisect_right

for _ in range(Q):
    l, r = list(map(int, input().split()))
    li = bisect_left(like_2017s, l)
    ri = bisect_right(like_2017s, r)
    print((ri - li))

Q = int(eval(input()))
import math


def sieve_of_erastosthenes(num):
    input_list = [
        False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num)
    ]
    input_list[0] = input_list[1] = False
    input_list[2] = input_list[3] = input_list[5] = True
    sqrt = math.sqrt(num)
    for serial in range(3, num, 2):
        if serial >= sqrt:
            return input_list
        for s in range(serial**2, num, serial):
            input_list[s] = False


primes = sieve_of_erastosthenes(10**5)
likes = []
for i in range(3, 10**5, 2):
    if primes[i] and primes[(i + 1) // 2]:
        likes.append(i)
from bisect import bisect_left, bisect_right

for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((bisect_right(likes, r) - bisect_left(likes, l)))

-from functools import lru_cache +import math -@lru_cache(maxsize=None) -def is_prime(n: int): -    if n == 2: -        return True -    if n == 1 or n % 2 == 0: -        return False -    for p in range(3, int(n**0.5) + 1, 2): -        if n % p == 0: -            return False -    return True +def sieve_of_erastosthenes(num): +    input_list = [ +        False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(num) +    ] +    input_list[0] = input_list[1] = False +    input_list[2] = input_list[3] = input_list[5] = True +    sqrt = math.sqrt(num) +    for serial in range(3, num, 2): +        if serial >= sqrt: +            return input_list +        for s in range(serial**2, num, serial): +            input_list[s] = False -like_2017s = [] +primes = sieve_of_erastosthenes(10**5) +likes = [] -    if is_prime(i) and is_prime((i + 1) // 2): -        like_2017s.append(i) +    if primes[i] and primes[(i + 1) // 2]: +        likes.append(i) -    li = bisect_left(like_2017s, l) -    ri = bisect_right(like_2017s, r) -    print((ri - li)) +    print((bisect_right(likes, r) - bisect_left(likes, l)))