Num = [int(i) for i in range(2, 100001)]

Primes = [True for i in range(100001)]

Sim = [0 for i in range(100001)]



for i in range(2, 100001):

    if Primes[i] == True:

        j = i * 2

        while j < 100001:

            Primes[j] = False

            j += i



for i in range(3, 100001):

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

        Sim[i] = Sim[i-1] + 1

    else:

        Sim[i] = Sim[i-1]



Q = int(eval(input()))

for i in range(Q):

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

    print((Sim[r] - Sim[l-1]))
import sys



def solve():

    input = sys.stdin.readline

    isPrime = [True] * (1 + 10**5)

    isPrime[0] = isPrime[1] = False

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



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

        if isPrime[i]:

            k = 2 * i

            while k <= 10 ** 5:

                isPrime[k] = False

                k += i

            if i % 2 == 1 and isPrime[(i + 1) // 2]: Like[i] = Like[i-1] + 1

            else: Like[i] = Like[i-1]

        else: Like[i] = Like[i-1]

                

    Q = int(eval(input()))

    for _ in range(Q):

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

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



    return 0



if __name__ == "__main__":

    solve()
Num = [int(i) for i in range(2, 100001)]
Primes = [True for i in range(100001)]
Sim = [0 for i in range(100001)]
for i in range(2, 100001):
    if Primes[i] == True:
        j = i * 2
        while j < 100001:
            Primes[j] = False
            j += i
for i in range(3, 100001):
    if Primes[i] and Primes[(i + 1) // 2]:
        Sim[i] = Sim[i - 1] + 1
    else:
        Sim[i] = Sim[i - 1]
Q = int(eval(input()))
for i in range(Q):
    l, r = list(map(int, input().split()))
    print((Sim[r] - Sim[l - 1]))

import sys


def solve():
    input = sys.stdin.readline
    isPrime = [True] * (1 + 10**5)
    isPrime[0] = isPrime[1] = False
    Like = [0] * (1 + 10**5)
    for i in range(2, 1 + 10**5):
        if isPrime[i]:
            k = 2 * i
            while k <= 10**5:
                isPrime[k] = False
                k += i
            if i % 2 == 1 and isPrime[(i + 1) // 2]:
                Like[i] = Like[i - 1] + 1
            else:
                Like[i] = Like[i - 1]
        else:
            Like[i] = Like[i - 1]
    Q = int(eval(input()))
    for _ in range(Q):
        l, r = list(map(int, input().split()))
        print((Like[r] - Like[l - 1]))
    return 0


if __name__ == "__main__":
    solve()

-Num = [int(i) for i in range(2, 100001)] -Primes = [True for i in range(100001)] -Sim = [0 for i in range(100001)] -for i in range(2, 100001): -    if Primes[i] == True: -        j = i * 2 -        while j < 100001: -            Primes[j] = False -            j += i -for i in range(3, 100001): -    if Primes[i] and Primes[(i + 1) // 2]: -        Sim[i] = Sim[i - 1] + 1 -    else: -        Sim[i] = Sim[i - 1] -Q = int(eval(input())) -for i in range(Q): -    l, r = list(map(int, input().split())) -    print((Sim[r] - Sim[l - 1])) +import sys + + +def solve(): +    input = sys.stdin.readline +    isPrime = [True] * (1 + 10**5) +    isPrime[0] = isPrime[1] = False +    Like = [0] * (1 + 10**5) +    for i in range(2, 1 + 10**5): +        if isPrime[i]: +            k = 2 * i +            while k <= 10**5: +                isPrime[k] = False +                k += i +            if i % 2 == 1 and isPrime[(i + 1) // 2]: +                Like[i] = Like[i - 1] + 1 +            else: +                Like[i] = Like[i - 1] +        else: +            Like[i] = Like[i - 1] +    Q = int(eval(input())) +    for _ in range(Q): +        l, r = list(map(int, input().split())) +        print((Like[r] - Like[l - 1])) +    return 0 + + +if __name__ == "__main__": +    solve()