Q=int(eval(input()))

A=[list(map(int,input().split())) for i in range(Q)]

B,C=list(zip(*A))

a=max(max(B),max(C))

def get_primenumber(N):

  prime_list=[2]

  for num in range(3,N+1,2):

    if all(num%prime != 0 for prime in prime_list):

      prime_list.append(num)

  return prime_list



X=get_primenumber(a)

P=[False]*(a+1)

L=[False]*(a+1)

for i in X:

  P[i]=True

for i in X:

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

    L[i]=True

C=[]

c=0

for i in range(a+1):

  if L[i]:

    c+=1

  C.append(c)

for s,t in A:

  print((C[t]-C[s-1]))
import math

Q=int(eval(input()))

A=[list(map(int,input().split())) for i in range(Q)]

B,C=list(zip(*A))

a=max(max(B),max(C))



def get_primenumber(n):

  prime=[]

  limit=math.sqrt(n)

  data=[i+1 for i in range(1, n)]

  while True:

    p=data[0]

    if limit<=p:

      return prime+data

    prime.append(p)

    data=[e for e in data if e % p != 0]

        

X=get_primenumber(a)

P=[False]*(a+1)

L=[False]*(a+1)

for i in X:

  P[i]=True

for i in X:

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

    L[i]=True

C=[]

c=0

for i in range(a+1):

  if L[i]:

    c+=1

  C.append(c)

for s,t in A:

  print((C[t]-C[s-1]))
Q = int(eval(input()))
A = [list(map(int, input().split())) for i in range(Q)]
B, C = list(zip(*A))
a = max(max(B), max(C))


def get_primenumber(N):
    prime_list = [2]
    for num in range(3, N + 1, 2):
        if all(num % prime != 0 for prime in prime_list):
            prime_list.append(num)
    return prime_list


X = get_primenumber(a)
P = [False] * (a + 1)
L = [False] * (a + 1)
for i in X:
    P[i] = True
for i in X:
    if P[(i + 1) // 2]:
        L[i] = True
C = []
c = 0
for i in range(a + 1):
    if L[i]:
        c += 1
    C.append(c)
for s, t in A:
    print((C[t] - C[s - 1]))

import math

Q = int(eval(input()))
A = [list(map(int, input().split())) for i in range(Q)]
B, C = list(zip(*A))
a = max(max(B), max(C))


def get_primenumber(n):
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]


X = get_primenumber(a)
P = [False] * (a + 1)
L = [False] * (a + 1)
for i in X:
    P[i] = True
for i in X:
    if P[(i + 1) // 2]:
        L[i] = True
C = []
c = 0
for i in range(a + 1):
    if L[i]:
        c += 1
    C.append(c)
for s, t in A:
    print((C[t] - C[s - 1]))

+import math + -def get_primenumber(N): -    prime_list = [2] -    for num in range(3, N + 1, 2): -        if all(num % prime != 0 for prime in prime_list): -            prime_list.append(num) -    return prime_list +def get_primenumber(n): +    prime = [] +    limit = math.sqrt(n) +    data = [i + 1 for i in range(1, n)] +    while True: +        p = data[0] +        if limit <= p: +            return prime + data +        prime.append(p) +        data = [e for e in data if e % p != 0]