Q=int(eval(input()))



fact=[True]*(10**5+1)

fact[0]=False

fact[1]=False



num=[0]*(10**5+1)

cur=0

for i in range(len(fact)):

  if fact[i]:

    for j in range(i*2,len(fact),i):

      fact[j]=False

    if fact[(i+1)//2]:

      cur+=1

  num[i]=cur

      

for i in range(Q):

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

  print((num[r]-num[l-1]))

import sys

readline = sys.stdin.readline



Q = int(readline())



# 10 ** 5までの「2017に似た数」を全て求めておく



fact = [True] * (10 ** 5 + 1)

fact[0] = False

fact[1] = False

like2017 = [0] * (10 ** 5 + 1)

for i in range(2, len(fact)):

  if fact[i]:

    if i % 2 == 1 and fact[(i + 1) // 2]:

      like2017[i] = 1

    for j in range(i * 2, len(fact), i):

      fact[j] = False

        

for i in range(1, len(like2017)):

  like2017[i] += like2017[i - 1]



for i in range(Q):

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

  print((like2017[r] - like2017[l - 1]))

Q = int(eval(input()))
fact = [True] * (10**5 + 1)
fact[0] = False
fact[1] = False
num = [0] * (10**5 + 1)
cur = 0
for i in range(len(fact)):
    if fact[i]:
        for j in range(i * 2, len(fact), i):
            fact[j] = False
        if fact[(i + 1) // 2]:
            cur += 1
    num[i] = cur
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((num[r] - num[l - 1]))

import sys

readline = sys.stdin.readline
Q = int(readline())
# 10 ** 5までの「2017に似た数」を全て求めておく
fact = [True] * (10**5 + 1)
fact[0] = False
fact[1] = False
like2017 = [0] * (10**5 + 1)
for i in range(2, len(fact)):
    if fact[i]:
        if i % 2 == 1 and fact[(i + 1) // 2]:
            like2017[i] = 1
        for j in range(i * 2, len(fact), i):
            fact[j] = False
for i in range(1, len(like2017)):
    like2017[i] += like2017[i - 1]
for i in range(Q):
    l, r = list(map(int, readline().split()))
    print((like2017[r] - like2017[l - 1]))

-Q = int(eval(input())) +import sys + +readline = sys.stdin.readline +Q = int(readline()) +# 10 ** 5までの「2017に似た数」を全て求めておく -num = [0] * (10**5 + 1) -cur = 0 -for i in range(len(fact)): +like2017 = [0] * (10**5 + 1) +for i in range(2, len(fact)): +        if i % 2 == 1 and fact[(i + 1) // 2]: +            like2017[i] = 1 -        if fact[(i + 1) // 2]: -            cur += 1 -    num[i] = cur +for i in range(1, len(like2017)): +    like2017[i] += like2017[i - 1] -    l, r = list(map(int, input().split())) -    print((num[r] - num[l - 1])) +    l, r = list(map(int, readline().split())) +    print((like2017[r] - like2017[l - 1]))