import math

from itertools import accumulate





def is_prime(n):

    if n == 1:

        return 0



    for k in range(2, int(math.sqrt(n)) + 1):

        if n % k == 0:

            return 0



    return 1





Q = int(eval(input()))

L = [0]*Q

R = [0]*Q



for i in range(Q):

    L[i], R[i] = list(map(int, input().split()))



min_L = min(L)

max_R = max(R)



check = []

for i in range(min_L, max_R+1):

    if (i % 2 == 1):

        flg = (is_prime(i) and is_prime((i+1)/2))

    else:

        flg = 0

    check.append(flg)



# 累積和

check = [0] + check

check = list(accumulate(check))



for i in range(Q):

    print((check[R[i] - min_L + 1] - check[L[i] - min_L]))
from itertools import accumulate





# エラトステネスの篩

# is_prime := 1~nが素数か否か

# table := 2~nのうち素数

def sieve(n):

    is_prime = [True for _ in range(n)]

    is_prime[0] = False



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

        if is_prime[i-1]:

            j = 2 * i

            while j <= n:

                is_prime[j-1] = False

                j += i

    table = [i for i in range(1, n+1) if is_prime[i-1]]

    return is_prime, table





Q = int(eval(input()))

L = [0]*Q

R = [0]*Q



for i in range(Q):

    L[i], R[i] = list(map(int, input().split()))



max_R = max(R)

is_prime, table = sieve(max_R)



check = [0]*(max_R + 1)

for i in range(0, max_R + 1):

    if (i % 2 == 1):

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

            check[i] = 1



# 累積和

check = [0] + check

check = list(accumulate(check))



for i in range(Q):

    print((check[R[i] + 1] - check[L[i]]))
import math
from itertools import accumulate


def is_prime(n):
    if n == 1:
        return 0
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return 0
    return 1


Q = int(eval(input()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))
min_L = min(L)
max_R = max(R)
check = []
for i in range(min_L, max_R + 1):
    if i % 2 == 1:
        flg = is_prime(i) and is_prime((i + 1) / 2)
    else:
        flg = 0
    check.append(flg)
# 累積和
check = [0] + check
check = list(accumulate(check))
for i in range(Q):
    print((check[R[i] - min_L + 1] - check[L[i] - min_L]))

from itertools import accumulate

# エラトステネスの篩
# is_prime := 1~nが素数か否か
# table := 2~nのうち素数
def sieve(n):
    is_prime = [True for _ in range(n)]
    is_prime[0] = False
    for i in range(2, n + 1):
        if is_prime[i - 1]:
            j = 2 * i
            while j <= n:
                is_prime[j - 1] = False
                j += i
    table = [i for i in range(1, n + 1) if is_prime[i - 1]]
    return is_prime, table


Q = int(eval(input()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))
max_R = max(R)
is_prime, table = sieve(max_R)
check = [0] * (max_R + 1)
for i in range(0, max_R + 1):
    if i % 2 == 1:
        if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]:
            check[i] = 1
# 累積和
check = [0] + check
check = list(accumulate(check))
for i in range(Q):
    print((check[R[i] + 1] - check[L[i]]))

-import math - -def is_prime(n): -    if n == 1: -        return 0 -    for k in range(2, int(math.sqrt(n)) + 1): -        if n % k == 0: -            return 0 -    return 1 +# エラトステネスの篩 +# is_prime := 1~nが素数か否か +# table := 2~nのうち素数 +def sieve(n): +    is_prime = [True for _ in range(n)] +    is_prime[0] = False +    for i in range(2, n + 1): +        if is_prime[i - 1]: +            j = 2 * i +            while j <= n: +                is_prime[j - 1] = False +                j += i +    table = [i for i in range(1, n + 1) if is_prime[i - 1]] +    return is_prime, table -min_L = min(L) -check = [] -for i in range(min_L, max_R + 1): +is_prime, table = sieve(max_R) +check = [0] * (max_R + 1) +for i in range(0, max_R + 1): -        flg = is_prime(i) and is_prime((i + 1) / 2) -    else: -        flg = 0 -    check.append(flg) +        if is_prime[i - 1] and is_prime[(i + 1) // 2 - 1]: +            check[i] = 1 -    print((check[R[i] - min_L + 1] - check[L[i] - min_L])) +    print((check[R[i] + 1] - check[L[i]]))