import math

def eratosthenes(limit):

    A = [i for i in range(2, limit+1)]

    P = []

    while True:

        prime = min(A)

        if prime > math.sqrt(limit):

            break

        P.append(prime)

        i = 0

        while i < len(A):

            if A[i] % prime == 0:

                A.pop(i)

                continue

            i += 1

    for a in A:

        P.append(a)

    return list(P)



a = eratosthenes(100000)

b = set([2*i-1 for i in a])

a = set(a)

chk = sorted(list(a&b))



from bisect import bisect,bisect_left

import sys

input = sys.stdin.readline



q = int(eval(input()))

for i in range(q):

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

  print((bisect(chk,r)-bisect_left(chk,l)))
def is_prime(q):

    if q == 2: return True

    if q < 2 or q&1 == 0: return False

    return pow(5, q-1, q)*pow(7, q-1, q) == 1

    

s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]

b = [5,7]

for i in range(2,10**5):

  if i in s:

    continue

  if is_prime(i):

    b.append(i)



a = set([2*i-1 for i in b])

b = set(b)

chk = sorted(list(a&b))

 

from bisect import bisect,bisect_left

import sys

input = sys.stdin.readline

 

q = int(eval(input()))

for i in range(q):

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

  print((bisect(chk,r)-bisect_left(chk,l)))
import math


def eratosthenes(limit):
    A = [i for i in range(2, limit + 1)]
    P = []
    while True:
        prime = min(A)
        if prime > math.sqrt(limit):
            break
        P.append(prime)
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
    for a in A:
        P.append(a)
    return list(P)


a = eratosthenes(100000)
b = set([2 * i - 1 for i in a])
a = set(a)
chk = sorted(list(a & b))
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((bisect(chk, r) - bisect_left(chk, l)))

def is_prime(q):
    if q == 2:
        return True
    if q < 2 or q & 1 == 0:
        return False
    return pow(5, q - 1, q) * pow(7, q - 1, q) == 1


s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831]
b = [5, 7]
for i in range(2, 10**5):
    if i in s:
        continue
    if is_prime(i):
        b.append(i)
a = set([2 * i - 1 for i in b])
b = set(b)
chk = sorted(list(a & b))
from bisect import bisect, bisect_left
import sys

input = sys.stdin.readline
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    print((bisect(chk, r) - bisect_left(chk, l)))

-import math +def is_prime(q): +    if q == 2: +        return True +    if q < 2 or q & 1 == 0: +        return False +    return pow(5, q - 1, q) * pow(7, q - 1, q) == 1 -def eratosthenes(limit): -    A = [i for i in range(2, limit + 1)] -    P = [] -    while True: -        prime = min(A) -        if prime > math.sqrt(limit): -            break -        P.append(prime) -        i = 0 -        while i < len(A): -            if A[i] % prime == 0: -                A.pop(i) -                continue -            i += 1 -    for a in A: -        P.append(a) -    return list(P) - - -a = eratosthenes(100000) -b = set([2 * i - 1 for i in a]) -a = set(a) +s = [561, 11041, 29341, 38081, 46657, 50737, 75361, 79381, 88831] +b = [5, 7] +for i in range(2, 10**5): +    if i in s: +        continue +    if is_prime(i): +        b.append(i) +a = set([2 * i - 1 for i in b]) +b = set(b)