def eratosthenes(n):

 is_p=[1]*n

# p_list=[]



 is_p[0]=0

 is_p[1]=0



 for i in range(2,n):

  if is_p[i]:

#   p_list.append(i)

   for j in range(i*i,n,i):

    is_p[j] = 0



 return is_p#, p_list



lim=10**5+1

#is_p, p_list=eratosthenes(lim)

is_p=eratosthenes(lim)



q=int(eval(input()))



'''

b=[0]

for i in range(1,lim+1):

 if is_p[i-1] and is_p[i//2]:

  b.append(b[i-1]+1)

 else:

  b.append(b[i-1])

'''

a = [0] * (10**5+2)

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

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

        a[i] = 1

for i in range(1, 10**5+1):

    a[i+1] += a[i]



for i in range(q):

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

# print(b[r+1]-b[l])

 print((a[r]-a[l-1]))
def eratosthenes(n):

 is_p=[1]*n

 p_list=[]



 is_p[0]=0

 is_p[1]=0



 for i in range(2,n):

  if is_p[i]:

   p_list.append(i)

   for j in range(i*i,n,i):

    is_p[j] = 0



 return is_p, p_list



lim=10**5+1

is_p, p_list=eratosthenes(lim)



q=int(eval(input()))



b=[0]

for i in range(1,lim+1):

 if is_p[i-1] and is_p[i//2]:

  b.append(b[i-1]+1)

 else:

  b.append(b[i-1])



import sys

stdin=sys.stdin

temp=lambda: list(map(int, stdin.readline().split()))



for i in range(q):

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

 l,r=temp()

 print((b[r+1]-b[l]))
def eratosthenes(n):
    is_p = [1] * n
    # p_list=[]
    is_p[0] = 0
    is_p[1] = 0
    for i in range(2, n):
        if is_p[i]:
            #   p_list.append(i)
            for j in range(i * i, n, i):
                is_p[j] = 0
    return is_p  # , p_list


lim = 10**5 + 1
# is_p, p_list=eratosthenes(lim)
is_p = eratosthenes(lim)
q = int(eval(input()))
"""
b=[0]
for i in range(1,lim+1):
 if is_p[i-1] and is_p[i//2]:
  b.append(b[i-1]+1)
 else:
  b.append(b[i-1])
"""
a = [0] * (10**5 + 2)
for i in range(3, 10**5 + 1, 2):
    if is_p[i] and is_p[(i + 1) // 2]:
        a[i] = 1
for i in range(1, 10**5 + 1):
    a[i + 1] += a[i]
for i in range(q):
    l, r = list(map(int, input().split()))
    # print(b[r+1]-b[l])
    print((a[r] - a[l - 1]))

def eratosthenes(n):
    is_p = [1] * n
    p_list = []
    is_p[0] = 0
    is_p[1] = 0
    for i in range(2, n):
        if is_p[i]:
            p_list.append(i)
            for j in range(i * i, n, i):
                is_p[j] = 0
    return is_p, p_list


lim = 10**5 + 1
is_p, p_list = eratosthenes(lim)
q = int(eval(input()))
b = [0]
for i in range(1, lim + 1):
    if is_p[i - 1] and is_p[i // 2]:
        b.append(b[i - 1] + 1)
    else:
        b.append(b[i - 1])
import sys

stdin = sys.stdin
temp = lambda: list(map(int, stdin.readline().split()))
for i in range(q):
    # l,r=map(int,input().split())
    l, r = temp()
    print((b[r + 1] - b[l]))

-    # p_list=[] +    p_list = [] -            #   p_list.append(i) +            p_list.append(i) -    return is_p  # , p_list +    return is_p, p_list -# is_p, p_list=eratosthenes(lim) -is_p = eratosthenes(lim) +is_p, p_list = eratosthenes(lim) -""" -b=[0] -for i in range(1,lim+1): - if is_p[i-1] and is_p[i//2]: -  b.append(b[i-1]+1) - else: -  b.append(b[i-1]) -""" -a = [0] * (10**5 + 2) -for i in range(3, 10**5 + 1, 2): -    if is_p[i] and is_p[(i + 1) // 2]: -        a[i] = 1 -for i in range(1, 10**5 + 1): -    a[i + 1] += a[i] +b = [0] +for i in range(1, lim + 1): +    if is_p[i - 1] and is_p[i // 2]: +        b.append(b[i - 1] + 1) +    else: +        b.append(b[i - 1]) +import sys + +stdin = sys.stdin +temp = lambda: list(map(int, stdin.readline().split())) -    l, r = list(map(int, input().split())) -    # print(b[r+1]-b[l]) -    print((a[r] - a[l - 1])) +    # l,r=map(int,input().split()) +    l, r = temp() +    print((b[r + 1] - b[l]))