d = [0]

ans = 0



def prime(n):

    if n == 1:

        return False

    i = 2

    while i * i <= n:

        if n % i == 0:

            return False

        else:

            i += 1

    return True

    

for i in range(10 ** 5 // 2):

    if prime(2 * i + 1) and prime(i + 1):

        ans += 1

    d.append(ans)



Q = int(eval(input()))



for _ in range(Q):

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

    print((d[r // 2 + 1] - d[l // 2 + 1 - 1]))
#!/usr/bin/env python3



Q = int(eval(input()))

my_max = 10 ** 5



nums = [i for i in range(2, my_max + 1)]

p = 2

idx = 0

while p * p <= my_max and idx < len(nums):

    nums = [n for n in nums if n % p != 0 or n == p]

    idx += 1

    p = nums[idx]

primes = set(nums)



ruiseki = [0]

total = 0

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

    if i % 2 == 1 and i in primes and int((i + 1) / 2) in primes:

        total += 1

    ruiseki.append(total)



for _ in range(Q):

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

    print((ruiseki[r] - ruiseki[l - 1]))
d = [0]
ans = 0


def prime(n):
    if n == 1:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        else:
            i += 1
    return True


for i in range(10**5 // 2):
    if prime(2 * i + 1) and prime(i + 1):
        ans += 1
    d.append(ans)
Q = int(eval(input()))
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((d[r // 2 + 1] - d[l // 2 + 1 - 1]))

#!/usr/bin/env python3
Q = int(eval(input()))
my_max = 10**5
nums = [i for i in range(2, my_max + 1)]
p = 2
idx = 0
while p * p <= my_max and idx < len(nums):
    nums = [n for n in nums if n % p != 0 or n == p]
    idx += 1
    p = nums[idx]
primes = set(nums)
ruiseki = [0]
total = 0
for i in range(1, my_max + 1):
    if i % 2 == 1 and i in primes and int((i + 1) / 2) in primes:
        total += 1
    ruiseki.append(total)
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((ruiseki[r] - ruiseki[l - 1]))

-d = [0] -ans = 0 - - -def prime(n): -    if n == 1: -        return False -    i = 2 -    while i * i <= n: -        if n % i == 0: -            return False -        else: -            i += 1 -    return True - - -for i in range(10**5 // 2): -    if prime(2 * i + 1) and prime(i + 1): -        ans += 1 -    d.append(ans) +#!/usr/bin/env python3 +my_max = 10**5 +nums = [i for i in range(2, my_max + 1)] +p = 2 +idx = 0 +while p * p <= my_max and idx < len(nums): +    nums = [n for n in nums if n % p != 0 or n == p] +    idx += 1 +    p = nums[idx] +primes = set(nums) +ruiseki = [0] +total = 0 +for i in range(1, my_max + 1): +    if i % 2 == 1 and i in primes and int((i + 1) / 2) in primes: +        total += 1 +    ruiseki.append(total) -    print((d[r // 2 + 1] - d[l // 2 + 1 - 1])) +    print((ruiseki[r] - ruiseki[l - 1]))