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

like=[False]*(10**5+1)

f[0]=False

f[1]=False

import math

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

  if not f[i]:

    continue

  fact=True

  for j in range(2,int(math.sqrt(i))+1):

    if i%j==0:

      fact=False

      break

  

  if fact:

    f[i]=True

    if i*2-1<len(like):

      like[i*2-1]=True

    for p in range(i*2,len(f),i):

      f[p]=False



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

cur=0

for i in range(len(sums)):

  if f[i] and like[i]:

    sums[i]=cur+1

    cur+=1

  else:

    sums[i]=cur



Q=int(eval(input()))

for i in range(Q):

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

  print((sums[r]-sums[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]))

f = [True] * (10**5 + 1)
like = [False] * (10**5 + 1)
f[0] = False
f[1] = False
import math

for i in range(2, len(f)):
    if not f[i]:
        continue
    fact = True
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            fact = False
            break
    if fact:
        f[i] = True
        if i * 2 - 1 < len(like):
            like[i * 2 - 1] = True
        for p in range(i * 2, len(f), i):
            f[p] = False
sums = [0] * (10**5 + 1)
cur = 0
for i in range(len(sums)):
    if f[i] and like[i]:
        sums[i] = cur + 1
        cur += 1
    else:
        sums[i] = cur
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((sums[r] - sums[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]))

-f = [True] * (10**5 + 1) -like = [False] * (10**5 + 1) -f[0] = False -f[1] = False -import math - -for i in range(2, len(f)): -    if not f[i]: -        continue -    fact = True -    for j in range(2, int(math.sqrt(i)) + 1): -        if i % j == 0: -            fact = False -            break -    if fact: -        f[i] = True -        if i * 2 - 1 < len(like): -            like[i * 2 - 1] = True -        for p in range(i * 2, len(f), i): -            f[p] = False -sums = [0] * (10**5 + 1) +Q = int(eval(input())) +fact = [True] * (10**5 + 1) +fact[0] = False +fact[1] = False +num = [0] * (10**5 + 1) -for i in range(len(sums)): -    if f[i] and like[i]: -        sums[i] = cur + 1 -        cur += 1 -    else: -        sums[i] = cur -Q = int(eval(input())) +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 -    print((sums[r] - sums[l - 1])) +    print((num[r] - num[l - 1]))