# import sys

import math



# import copy

# import heapq

# from collections import deque

# import decimal



# sys.setrecursionlimit(100001)

# INF = sys.maxsize



# ===CODE===

q = int(eval(input()))



condition = 10 ** 5



data = []

for i in range(q):

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

    data.append((l, r))



kodoku = {2}



for i in range(3, condition + 5, 2):

    lim = i ** (1 / 2)

    flg = True

    for j in range(2, int(lim)+1):

        # if div > lim:

        #     break

        if i % j == 0:

            flg = False

            break



    if flg:

        kodoku.add(i)



ruisekiwa = [0] * (condition + 5)



for i in range(3, condition + 5):

    ruisekiwa[i] = ruisekiwa[i - 1]

    if i in kodoku and (i + 1) // 2 in kodoku:

        ruisekiwa[i] += 1



for l, r in data:

    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]

    print(ans)

# import sys

import math



# import copy

# import heapq

# from collections import deque

# import decimal



# sys.setrecursionlimit(100001)

# INF = sys.maxsize



# ===CODE===

q = int(eval(input()))



condition = 10 ** 5



data = []

for i in range(q):

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

    data.append((l, r))



kodoku = {2}

kodoku_2 = [2]



for i in range(3, condition + 5, 2):

    lim = i ** (1 / 2)

    flg = True

    for div in kodoku_2:

        if div > lim:

            break

        if i % div == 0:

            flg = False

            break



    if flg:

        kodoku.add(i)

        kodoku_2.append(i)



ruisekiwa = [0] * (condition + 5)



for i in range(3, condition + 5):

    ruisekiwa[i] = ruisekiwa[i - 1]

    if i in kodoku and (i + 1) // 2 in kodoku:

        ruisekiwa[i] += 1



for l, r in data:

    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]

    print(ans)

# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal
# sys.setrecursionlimit(100001)
# INF = sys.maxsize
# ===CODE===
q = int(eval(input()))
condition = 10**5
data = []
for i in range(q):
    l, r = list(map(int, input().split()))
    data.append((l, r))
kodoku = {2}
for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for j in range(2, int(lim) + 1):
        # if div > lim:
        #     break
        if i % j == 0:
            flg = False
            break
    if flg:
        kodoku.add(i)
ruisekiwa = [0] * (condition + 5)
for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1
for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)

# import sys
import math

# import copy
# import heapq
# from collections import deque
# import decimal
# sys.setrecursionlimit(100001)
# INF = sys.maxsize
# ===CODE===
q = int(eval(input()))
condition = 10**5
data = []
for i in range(q):
    l, r = list(map(int, input().split()))
    data.append((l, r))
kodoku = {2}
kodoku_2 = [2]
for i in range(3, condition + 5, 2):
    lim = i ** (1 / 2)
    flg = True
    for div in kodoku_2:
        if div > lim:
            break
        if i % div == 0:
            flg = False
            break
    if flg:
        kodoku.add(i)
        kodoku_2.append(i)
ruisekiwa = [0] * (condition + 5)
for i in range(3, condition + 5):
    ruisekiwa[i] = ruisekiwa[i - 1]
    if i in kodoku and (i + 1) // 2 in kodoku:
        ruisekiwa[i] += 1
for l, r in data:
    ans = ruisekiwa[r] - ruisekiwa[max(0, l - 1)]
    print(ans)

+kodoku_2 = [2] -    for j in range(2, int(lim) + 1): -        # if div > lim: -        #     break -        if i % j == 0: +    for div in kodoku_2: +        if div > lim: +            break +        if i % div == 0: +        kodoku_2.append(i)