from math import sqrt



max_lr = 10 ** 5



sieve = [True] * (max_lr + 1)

sieve[0] = False

sieve[1] = False

for i in range(2, int(sqrt(max_lr)) + 1):

    if not sieve[i]:

        continue

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

        sieve[j] = False



cs = [0] * (max_lr + 1)

for i in range(3, max_lr + 1, 2):

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

        cs[i] = 1

for i in range(1, max_lr + 1):

    cs[i] += cs[i - 1]



Q = int(eval(input()))

for _ in range(Q):

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

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

# エラトステネスの篩, 累積和

def make_prime_table(N):

    sieve = [0] * (N + 1)

    sieve[0] = -1

    sieve[1] = -1

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

        if sieve[i] != 0:

            continue

        sieve[i] = i

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

            if sieve[j] == 0:

                sieve[j] = i

    return sieve



max_lr = 10 ** 5



prime_table = make_prime_table(max_lr)



cs = [0] * (max_lr + 1)

for i in range(3, max_lr + 1, 2):

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

        cs[i] = 1

for i in range(1, max_lr + 1):

    cs[i] += cs[i - 1]



Q = int(eval(input()))

for _ in range(Q):

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

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

from math import sqrt

max_lr = 10**5
sieve = [True] * (max_lr + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(sqrt(max_lr)) + 1):
    if not sieve[i]:
        continue
    for j in range(i * i, max_lr + 1, i):
        sieve[j] = False
cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if sieve[i] and sieve[(i + 1) // 2]:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))

# エラトステネスの篩, 累積和
def make_prime_table(N):
    sieve = [0] * (N + 1)
    sieve[0] = -1
    sieve[1] = -1
    for i in range(2, N + 1):
        if sieve[i] != 0:
            continue
        sieve[i] = i
        for j in range(i * i, N + 1, i):
            if sieve[j] == 0:
                sieve[j] = i
    return sieve


max_lr = 10**5
prime_table = make_prime_table(max_lr)
cs = [0] * (max_lr + 1)
for i in range(3, max_lr + 1, 2):
    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2:
        cs[i] = 1
for i in range(1, max_lr + 1):
    cs[i] += cs[i - 1]
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))

-from math import sqrt +# エラトステネスの篩, 累積和 +def make_prime_table(N): +    sieve = [0] * (N + 1) +    sieve[0] = -1 +    sieve[1] = -1 +    for i in range(2, N + 1): +        if sieve[i] != 0: +            continue +        sieve[i] = i +        for j in range(i * i, N + 1, i): +            if sieve[j] == 0: +                sieve[j] = i +    return sieve + -sieve = [True] * (max_lr + 1) -sieve[0] = False -sieve[1] = False -for i in range(2, int(sqrt(max_lr)) + 1): -    if not sieve[i]: -        continue -    for j in range(i * i, max_lr + 1, i): -        sieve[j] = False +prime_table = make_prime_table(max_lr) -    if sieve[i] and sieve[(i + 1) // 2]: +    if prime_table[i] == i and prime_table[(i + 1) // 2] == (i + 1) // 2: