Buggy python submission (verdict: Time Limit Exceeded):
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

maximum = 100000
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if v and i >= l and i > 1 and i <= r and i % 2 == 1 and primes[(i + 1) // 2]:
            count += 1
    print(count)


Fixed submission:
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
minimum = 0
primes = sieve(maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)


Fixed submission:
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime
                

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
primes = segment_sieve(minimum, maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)


Fixed submission:
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime
                

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
primes = segment_sieve(minimum, maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)


Fixed submission:
import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])