from math import gcd

from collections import deque

from bisect import bisect_left,bisect_right



q=int(eval(input()))

lr=[tuple(map(int,input().split())) for _ in range(q)]



rmax=max(e[1] for e in lr)

anslst=[]

candlst=deque([2])

pprod=2

for i in range(3,rmax+1,2):

  tmp=2*candlst[0]-1

  if gcd(pprod,i)==1: 

    candlst.append(i)

    pprod*=i

    if tmp==i:

      anslst.append(tmp)

  if tmp==i:

    candlst.popleft()



for e in lr:

  print((bisect_right(anslst,e[1])-bisect_left(anslst,e[0])))
q=int(eval(input()))

lr=[tuple(map(int,input().split())) for _ in range(q)]



n=10**5

ansl=[]

sieve=[1]*(n+1)

sieve[0],sieve[1]=0,0

for i in range(2,n):

  if sieve[i]:

    for j in range(2*i,n+1,i):

      sieve[j]=0

ans=[0]*(n+1)

for i in range(3,n):

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

    ans[i]=ans[i-1]+1

  else:

    ans[i]=ans[i-1]



for e in lr:

  print((ans[e[1]]-ans[e[0]-1]))

from math import gcd
from collections import deque
from bisect import bisect_left, bisect_right

q = int(eval(input()))
lr = [tuple(map(int, input().split())) for _ in range(q)]
rmax = max(e[1] for e in lr)
anslst = []
candlst = deque([2])
pprod = 2
for i in range(3, rmax + 1, 2):
    tmp = 2 * candlst[0] - 1
    if gcd(pprod, i) == 1:
        candlst.append(i)
        pprod *= i
        if tmp == i:
            anslst.append(tmp)
    if tmp == i:
        candlst.popleft()
for e in lr:
    print((bisect_right(anslst, e[1]) - bisect_left(anslst, e[0])))

q = int(eval(input()))
lr = [tuple(map(int, input().split())) for _ in range(q)]
n = 10**5
ansl = []
sieve = [1] * (n + 1)
sieve[0], sieve[1] = 0, 0
for i in range(2, n):
    if sieve[i]:
        for j in range(2 * i, n + 1, i):
            sieve[j] = 0
ans = [0] * (n + 1)
for i in range(3, n):
    if sieve[i] == 1 and sieve[(i + 1) // 2] == 1:
        ans[i] = ans[i - 1] + 1
    else:
        ans[i] = ans[i - 1]
for e in lr:
    print((ans[e[1]] - ans[e[0] - 1]))

-from math import gcd -from collections import deque -from bisect import bisect_left, bisect_right - -rmax = max(e[1] for e in lr) -anslst = [] -candlst = deque([2]) -pprod = 2 -for i in range(3, rmax + 1, 2): -    tmp = 2 * candlst[0] - 1 -    if gcd(pprod, i) == 1: -        candlst.append(i) -        pprod *= i -        if tmp == i: -            anslst.append(tmp) -    if tmp == i: -        candlst.popleft() +n = 10**5 +ansl = [] +sieve = [1] * (n + 1) +sieve[0], sieve[1] = 0, 0 +for i in range(2, n): +    if sieve[i]: +        for j in range(2 * i, n + 1, i): +            sieve[j] = 0 +ans = [0] * (n + 1) +for i in range(3, n): +    if sieve[i] == 1 and sieve[(i + 1) // 2] == 1: +        ans[i] = ans[i - 1] + 1 +    else: +        ans[i] = ans[i - 1] -    print((bisect_right(anslst, e[1]) - bisect_left(anslst, e[0]))) +    print((ans[e[1]] - ans[e[0] - 1]))