# D

N = 10**5

primes = set([])

is_prime = [True]*(N+1)

is_prime[0] = False

is_prime[1] = False

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

    if is_prime[i]:

        primes.add(i)

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

            is_prime[j*i] = False

    

# like-2017

cnt = [0]*(int(1e5)+2)

for p in primes:

    if (p+1)//2 in primes:

        cnt[p] = 1

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

    cnt[i] += cnt[i-1]

#print(cnt[:100])

    

Q = int(eval(input()))

for _ in range(Q):

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

    print((cnt[r]-cnt[l-1]))
# D

N = 10**5

primes = set([])

is_prime = [True]*(N+2)

is_prime[0] = False

is_prime[1] = False

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

    if is_prime[i]:

        primes.add(i)

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

            is_prime[j*i] = False

    

# like-2017

cnt = [0]*(N+2)

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

    cnt[i] += cnt[i-1]

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

        cnt[i] += 1

#print(cnt[:100])

    

Q = int(eval(input()))

for _ in range(Q):

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

    print((cnt[r]-cnt[l-1]))
# D
N = 10**5
primes = set([])
is_prime = [True] * (N + 1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N + 1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N // i + 1):
            is_prime[j * i] = False
# like-2017
cnt = [0] * (int(1e5) + 2)
for p in primes:
    if (p + 1) // 2 in primes:
        cnt[p] = 1
for i in range(1, int(1e5) + 2):
    cnt[i] += cnt[i - 1]
# print(cnt[:100])
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cnt[r] - cnt[l - 1]))

# D
N = 10**5
primes = set([])
is_prime = [True] * (N + 2)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N + 2):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N // i + 1):
            is_prime[j * i] = False
# like-2017
cnt = [0] * (N + 2)
for i in range(1, N + 2):
    cnt[i] += cnt[i - 1]
    if is_prime[i] and is_prime[(i + 1) // 2]:
        cnt[i] += 1
# print(cnt[:100])
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cnt[r] - cnt[l - 1]))

-is_prime = [True] * (N + 1) +is_prime = [True] * (N + 2) -for i in range(2, N + 1): +for i in range(2, N + 2): -cnt = [0] * (int(1e5) + 2) -for p in primes: -    if (p + 1) // 2 in primes: -        cnt[p] = 1 -for i in range(1, int(1e5) + 2): +cnt = [0] * (N + 2) +for i in range(1, N + 2): +    if is_prime[i] and is_prime[(i + 1) // 2]: +        cnt[i] += 1