import numpy as np



q = int(eval(input()))



# 高速素数判定

is_prime = np.ones(100001, dtype=int)

is_prime[0]=0

is_prime[1]=0



for i in range(2,100001):

    if is_prime[i]==1:

        j=i+i

        while j <= 100000:

            is_prime[j] = 0

            j += i



like2017 = [is_prime[x]*is_prime[(x+1)//2] for x in range(0,100001)]



for i in range(1,100001):

    like2017[i] += like2017[i-1]

for i in range(q):

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

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

import numpy as np



q = int(eval(input()))



# 高速素数判定

is_prime = np.ones(100001, dtype=int)

is_prime[0]=0

is_prime[1]=0



for i in range(2,100001):

    if is_prime[i]==1:

        j=i+i

        while j <= 100000:

            is_prime[j] = 0

            j += i



like2017 = [1 if is_prime[i] and is_prime[(i+1)//2] else 0 for i in range(0,100001) ]



for i in range(1,100001):

    like2017[i] += like2017[i-1]

for i in range(q):

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

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

import numpy as np

q = int(eval(input()))
# 高速素数判定
is_prime = np.ones(100001, dtype=int)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2, 100001):
    if is_prime[i] == 1:
        j = i + i
        while j <= 100000:
            is_prime[j] = 0
            j += i
like2017 = [is_prime[x] * is_prime[(x + 1) // 2] for x in range(0, 100001)]
for i in range(1, 100001):
    like2017[i] += like2017[i - 1]
for i in range(q):
    l, r = list(map(int, input().split()))
    print((like2017[r] - like2017[l - 1]))

import numpy as np

q = int(eval(input()))
# 高速素数判定
is_prime = np.ones(100001, dtype=int)
is_prime[0] = 0
is_prime[1] = 0
for i in range(2, 100001):
    if is_prime[i] == 1:
        j = i + i
        while j <= 100000:
            is_prime[j] = 0
            j += i
like2017 = [
    1 if is_prime[i] and is_prime[(i + 1) // 2] else 0 for i in range(0, 100001)
]
for i in range(1, 100001):
    like2017[i] += like2017[i - 1]
for i in range(q):
    l, r = list(map(int, input().split()))
    print((like2017[r] - like2017[l - 1]))

-like2017 = [is_prime[x] * is_prime[(x + 1) // 2] for x in range(0, 100001)] +like2017 = [ +    1 if is_prime[i] and is_prime[(i + 1) // 2] else 0 for i in range(0, 100001) +]