Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    q = 2*p
    while q <= max(r):
        if q in A:
            A.remove(q)
        q += p
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])


Fixed submission:
import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])


Fixed submission:
import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

Q = int(input())
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i],r[i] = map(int,input().split())

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])


Fixed submission:
import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate

Q = int(input())
L = [0]*Q
R = [0]*Q

for i in range(Q):
    L[i], R[i] = map(int,input().split())

r = max(R)
A = list(range(2, r+1))
sqrt_r = r**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_r:
        break
    check_numbers = A[idx+1:]
    for check_number in check_numbers:
        if check_number % p == 0:
            A.remove(check_number)
    idx += 1

B = [0]*(r+1)
for i in A:
    if int((i+1)/2) in A:
        B[i] = 1

B = list(accumulate(B))

for i,j in zip(L,R):
    print(B[j]-B[i-1])


Fixed submission:
import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)