import sys

import math

input = sys.stdin.readline





def eratosthenes(limit):

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

    P = []



    for i in range(65):

        prime = min(A)



        if prime > math.sqrt(limit):

            break



        P.append(prime)

        for j in range(limit):

            if j >= len(A):

                break

            if A[j] % prime == 0:

                A.pop(j)

                continue



    for a in A:

        P.append(a)



    return P





def binary_search(list, item):

    low = 0

    high = len(list) - 1



    while low <= high:

        mid = (low + high) // 2

        guess = list[mid]

        if guess == item:

            return True

        if guess > item:

            high = mid - 1

        else:

            low = mid + 1

    # 見つからなかったとき

    return None





MAX = 10 ** 5

prime_list = eratosthenes(MAX)

cumsum = [0] * ((MAX + 1) // 2)

cnt = 0



for i in range(1, MAX, 2):

    if binary_search(prime_list, i) and binary_search(prime_list, (i + 1) / 2):

        cnt += 1

    cumsum[(i - 1) // 2] = cnt



q = int(eval(input()))

for i in range(q):

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

    if l == 1:

        ans = cumsum[(r - 1) // 2]

    else:

        ans = cumsum[(r - 1) // 2] - cumsum[(l - 3) // 2]

    print(ans)
import sys

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines

sys.setrecursionlimit(10 ** 7)





def makePrimeChecker(n):

    isPrime = [True] * (n + 1)

    isPrime[0] = False

    isPrime[1] = False

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

        if isPrime[i]:

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

                isPrime[j] = False

    return isPrime





q = int(readline())

primelist = makePrimeChecker(10 ** 5 + 2)

check = [0] * (10 ** 5 + 1)

for i in range(1, 10 ** 5 + 1):

    if i % 2 == 1:

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

            check[i] += 1

    check[i] += check[i - 1]

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

for l, r in lr:

    print((check[r] - check[l - 1]))

import sys
import math

input = sys.stdin.readline


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


def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return True
        if guess > item:
            high = mid - 1
        else:
            low = mid + 1
    # 見つからなかったとき
    return None


MAX = 10**5
prime_list = eratosthenes(MAX)
cumsum = [0] * ((MAX + 1) // 2)
cnt = 0
for i in range(1, MAX, 2):
    if binary_search(prime_list, i) and binary_search(prime_list, (i + 1) / 2):
        cnt += 1
    cumsum[(i - 1) // 2] = cnt
q = int(eval(input()))
for i in range(q):
    l, r = list(map(int, input().split()))
    if l == 1:
        ans = cumsum[(r - 1) // 2]
    else:
        ans = cumsum[(r - 1) // 2] - cumsum[(l - 3) // 2]
    print(ans)

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**7)


def makePrimeChecker(n):
    isPrime = [True] * (n + 1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if isPrime[i]:
            for j in range(i * i, n + 1, i):
                isPrime[j] = False
    return isPrime


q = int(readline())
primelist = makePrimeChecker(10**5 + 2)
check = [0] * (10**5 + 1)
for i in range(1, 10**5 + 1):
    if i % 2 == 1:
        if primelist[i] and primelist[(i + 1) // 2]:
            check[i] += 1
    check[i] += check[i - 1]
lr = [list(map(int, readline().split())) for _ in range(q)]
for l, r in lr:
    print((check[r] - check[l - 1]))

-import math -input = sys.stdin.readline +read = sys.stdin.buffer.read +readline = sys.stdin.buffer.readline +readlines = sys.stdin.buffer.readlines +sys.setrecursionlimit(10**7) -def eratosthenes(limit): -    A = [i for i in range(2, limit + 1)] -    P = [] -    for i in range(65): -        prime = min(A) -        if prime > math.sqrt(limit): -            break -        P.append(prime) -        for j in range(limit): -            if j >= len(A): -                break -            if A[j] % prime == 0: -                A.pop(j) -                continue -    for a in A: -        P.append(a) -    return P +def makePrimeChecker(n): +    isPrime = [True] * (n + 1) +    isPrime[0] = False +    isPrime[1] = False +    for i in range(2, int(n**0.5) + 1): +        if isPrime[i]: +            for j in range(i * i, n + 1, i): +                isPrime[j] = False +    return isPrime -def binary_search(list, item): -    low = 0 -    high = len(list) - 1 -    while low <= high: -        mid = (low + high) // 2 -        guess = list[mid] -        if guess == item: -            return True -        if guess > item: -            high = mid - 1 -        else: -            low = mid + 1 -    # 見つからなかったとき -    return None - - -MAX = 10**5 -prime_list = eratosthenes(MAX) -cumsum = [0] * ((MAX + 1) // 2) -cnt = 0 -for i in range(1, MAX, 2): -    if binary_search(prime_list, i) and binary_search(prime_list, (i + 1) / 2): -        cnt += 1 -    cumsum[(i - 1) // 2] = cnt -q = int(eval(input())) -for i in range(q): -    l, r = list(map(int, input().split())) -    if l == 1: -        ans = cumsum[(r - 1) // 2] -    else: -        ans = cumsum[(r - 1) // 2] - cumsum[(l - 3) // 2] -    print(ans) +q = int(readline()) +primelist = makePrimeChecker(10**5 + 2) +check = [0] * (10**5 + 1) +for i in range(1, 10**5 + 1): +    if i % 2 == 1: +        if primelist[i] and primelist[(i + 1) // 2]: +            check[i] += 1 +    check[i] += check[i - 1] +lr = [list(map(int, readline().split())) for _ in range(q)] +for l, r in lr: +    print((check[r] - check[l - 1]))