import math

Q = int(eval(input()))



ps = []

maxfac = math.sqrt(10**5)

nums = [i+1 for i in range(1, 10**5)]

while True:

    p = nums[0]

    if maxfac <= p:

        break

    ps.append(p) 

    nums = [num for num in nums if num % p != 0]



ps = set(ps + nums)



c = [0] * 10**5

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

    if i in ps and (i+1)//2 in ps:

        c[i] = 1



from itertools import accumulate

cs = list(accumulate(c))



for _ in range(Q):

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

    print((cs[r] - cs[l-1]))
Q = int(eval(input()))

maxn = 10**5

is_prime = [True if i%2 == 1 else False for i in range(0, maxn+1) ]

is_prime[0] = False

is_prime[1] = False

is_prime[2] = True

for i in range(3, int(maxn**0.5) + 1, 2):

    if not is_prime[i]:

        continue

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

        is_prime[j] = False



ps = [i for i in range(maxn+1) if is_prime[i]]

ps = set(ps)



c = [0] * 10**5

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

    if i in ps and (i+1)//2 in ps:

        c[i] = 1



from itertools import accumulate

cs = list(accumulate(c))



for _ in range(Q):

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

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

import math

Q = int(eval(input()))
ps = []
maxfac = math.sqrt(10**5)
nums = [i + 1 for i in range(1, 10**5)]
while True:
    p = nums[0]
    if maxfac <= p:
        break
    ps.append(p)
    nums = [num for num in nums if num % p != 0]
ps = set(ps + nums)
c = [0] * 10**5
for i in range(3, 10**5 + 1, 2):
    if i in ps and (i + 1) // 2 in ps:
        c[i] = 1
from itertools import accumulate

cs = list(accumulate(c))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))

Q = int(eval(input()))
maxn = 10**5
is_prime = [True if i % 2 == 1 else False for i in range(0, maxn + 1)]
is_prime[0] = False
is_prime[1] = False
is_prime[2] = True
for i in range(3, int(maxn**0.5) + 1, 2):
    if not is_prime[i]:
        continue
    for j in range(i * 2, maxn + 1, i):
        is_prime[j] = False
ps = [i for i in range(maxn + 1) if is_prime[i]]
ps = set(ps)
c = [0] * 10**5
for i in range(3, 10**5 + 1, 2):
    if i in ps and (i + 1) // 2 in ps:
        c[i] = 1
from itertools import accumulate

cs = list(accumulate(c))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((cs[r] - cs[l - 1]))

-import math - -ps = [] -maxfac = math.sqrt(10**5) -nums = [i + 1 for i in range(1, 10**5)] -while True: -    p = nums[0] -    if maxfac <= p: -        break -    ps.append(p) -    nums = [num for num in nums if num % p != 0] -ps = set(ps + nums) +maxn = 10**5 +is_prime = [True if i % 2 == 1 else False for i in range(0, maxn + 1)] +is_prime[0] = False +is_prime[1] = False +is_prime[2] = True +for i in range(3, int(maxn**0.5) + 1, 2): +    if not is_prime[i]: +        continue +    for j in range(i * 2, maxn + 1, i): +        is_prime[j] = False +ps = [i for i in range(maxn + 1) if is_prime[i]] +ps = set(ps)