from functools import lru_cache

@lru_cache(maxsize=None)

def is_prime(x):

    if x==1:

        return False

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

        if x%i==0:

            return False

    return True



# @lru_cache(maxsize=None)

def like2017(x):

    return is_prime(i) and is_prime((i+1)//2)

    

table=[0,0]

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

    table+=table[i-1]+like2017(i),

        

n=int(eval(input()))

for _ in range(n):

    a,b=list(map(int,input().split()))

    print((table[b]-table[a-1]))

# print(table)

#from functools import lru_cache

#@lru_cache(maxsize=None)

def is_prime(x):

    if x==1:

        return False

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

        if x%i==0:

            return False

    return True



# @lru_cache(maxsize=None)

def like2017(x):

    return is_prime(i) and is_prime((i+1)//2)

    

table=[0,0]

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

    table+=table[i-1]+like2017(i),

        

n=int(eval(input()))

for _ in range(n):

    a,b=list(map(int,input().split()))

    print((table[b]-table[a-1]))

# print(table)

from functools import lru_cache


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


# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i + 1) // 2)


table = [0, 0]
for i in range(2, 10**5):
    table += (table[i - 1] + like2017(i),)
n = int(eval(input()))
for _ in range(n):
    a, b = list(map(int, input().split()))
    print((table[b] - table[a - 1]))
# print(table)

# from functools import lru_cache
# @lru_cache(maxsize=None)
def is_prime(x):
    if x == 1:
        return False
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return False
    return True


# @lru_cache(maxsize=None)
def like2017(x):
    return is_prime(i) and is_prime((i + 1) // 2)


table = [0, 0]
for i in range(2, 10**5):
    table += (table[i - 1] + like2017(i),)
n = int(eval(input()))
for _ in range(n):
    a, b = list(map(int, input().split()))
    print((table[b] - table[a - 1]))
# print(table)

-from functools import lru_cache - - -@lru_cache(maxsize=None) +# from functools import lru_cache +# @lru_cache(maxsize=None)