from bisect import bisect, bisect_left





size = 10 ** 5 + 1



is_prime = [True] * size

is_prime[0] = is_prime[1] = False



# √size まで

for i in range(2, 317):

  j = 2 * i

  while j < size:

    is_prime[j] = False

    j += i



# 先に like_numbers のテーブルを作っておく    

like_numbers = [

  i 

  for i, x in enumerate(is_prime)

  if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]

]



Q = int(eval(input()))



for _ in range(Q):

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

  # l から r まで探索してると 10^5 かかって間に合わないので二分探索を行う

  print((bisect(like_numbers, r) - bisect_left(like_numbers, l)))  

  
from itertools import count



N = 10 ** 5 + 10



is_prime = [True] * N

is_prime[0] = is_prime[1] = False



# ほぼO(N)

for i in range(N):

  if is_prime[i]:

    for j in count(2 * i, i):

      if j >= N:

        break

      is_prime[j] = False

      

is_2017_like_number = [0] * N



# O(N)

for i in range(N):

  if i % 2 != 0 and is_prime[i] and is_prime[(i + 1) // 2]:

    is_2017_like_number[i] = 1

    

cusum = [0] * (N + 1)



for i in range(N):

  cusum[i + 1] = cusum[i] + is_2017_like_number[i]

  

Q = int(eval(input()))



for _ in range(Q):

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

  r += 1  # 操作しやすいように [l, r) にする

  

  print((cusum[r] - cusum[l]))

  
from bisect import bisect, bisect_left

size = 10**5 + 1
is_prime = [True] * size
is_prime[0] = is_prime[1] = False
# √size まで
for i in range(2, 317):
    j = 2 * i
    while j < size:
        is_prime[j] = False
        j += i
# 先に like_numbers のテーブルを作っておく
like_numbers = [
    i
    for i, x in enumerate(is_prime)
    if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2]
]
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    # l から r まで探索してると 10^5 かかって間に合わないので二分探索を行う
    print((bisect(like_numbers, r) - bisect_left(like_numbers, l)))

from itertools import count

N = 10**5 + 10
is_prime = [True] * N
is_prime[0] = is_prime[1] = False
# ほぼO(N)
for i in range(N):
    if is_prime[i]:
        for j in count(2 * i, i):
            if j >= N:
                break
            is_prime[j] = False
is_2017_like_number = [0] * N
# O(N)
for i in range(N):
    if i % 2 != 0 and is_prime[i] and is_prime[(i + 1) // 2]:
        is_2017_like_number[i] = 1
cusum = [0] * (N + 1)
for i in range(N):
    cusum[i + 1] = cusum[i] + is_2017_like_number[i]
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    r += 1  # 操作しやすいように [l, r) にする
    print((cusum[r] - cusum[l]))

-from bisect import bisect, bisect_left +from itertools import count -size = 10**5 + 1 -is_prime = [True] * size +N = 10**5 + 10 +is_prime = [True] * N -# √size まで -for i in range(2, 317): -    j = 2 * i -    while j < size: -        is_prime[j] = False -        j += i -# 先に like_numbers のテーブルを作っておく -like_numbers = [ -    i -    for i, x in enumerate(is_prime) -    if x and (i + 1) % 2 == 0 and is_prime[(i + 1) // 2] -] +# ほぼO(N) +for i in range(N): +    if is_prime[i]: +        for j in count(2 * i, i): +            if j >= N: +                break +            is_prime[j] = False +is_2017_like_number = [0] * N +# O(N) +for i in range(N): +    if i % 2 != 0 and is_prime[i] and is_prime[(i + 1) // 2]: +        is_2017_like_number[i] = 1 +cusum = [0] * (N + 1) +for i in range(N): +    cusum[i + 1] = cusum[i] + is_2017_like_number[i] -    # l から r まで探索してると 10^5 かかって間に合わないので二分探索を行う -    print((bisect(like_numbers, r) - bisect_left(like_numbers, l))) +    r += 1  # 操作しやすいように [l, r) にする +    print((cusum[r] - cusum[l]))