Buggy python submission (verdict: Time Limit Exceeded):
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return [i for i in range(ub+1) if prime[i]]

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if i in primes and (i+1) // 2 in primes:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cum_sum[r] - cum_sum[l-1]
    print(ans)

Fixed submission:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return prime

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if primes[i] and primes[(i+1) // 2]:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cum_sum[r] - cum_sum[l-1]
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import random
from math import sqrt, ceil

def is_prime(N):
    temp = [True]*(N+1)
    temp[0] = temp[1] = False
    for i in range(2, ceil(sqrt(N+1))):
        if temp[i]:
            temp[i+i::i] = [False]*(len(temp[i+i::i]))
    if not temp[N]:
        return False
    return True

# スペース区切りの整数の入力
Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    
    for num in range(l, r+1, 2):
        if is_prime(num) and is_prime((num + 1)//2):
            ans += 1
    
    print(ans)

Fixed submission:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return prime

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if primes[i] and primes[(i+1) // 2]:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cum_sum[r] - cum_sum[l-1]
    print(ans)

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

def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True

# スペース区切りの整数の入力
Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    
    for num in range(l, r+1, 2):
        if is_prime(num) and is_prime((num + 1)//2):
            ans += 1
    
    print(ans)

Fixed submission:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return prime

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if primes[i] and primes[(i+1) // 2]:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cum_sum[r] - cum_sum[l-1]
    print(ans)

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

# Miller-Rabin test
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q&1 == 0:
        return False

    d = (q-1)>>1
    while d&1 == 0:
        d >>= 1

    for i in range(k):
        a = random.randint(1,q-1)
        t = d
        y = pow(a,t,q)
        
        while t != q-1 and y != 1 and y != q-1: 
            y = pow(y,2,q)
            t <<= 1
        if y != q-1 and t&1 == 0:
            return False
    return True

# スペース区切りの整数の入力
Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    ans = 0
    
    for num in range(l, r+1, 2):
        if is_prime(num) and is_prime((num + 1)//2):
            ans += 1
    
    print(ans)

Fixed submission:
def sieve_of_eratosthenes(ub):
    # O(n loglog n) implementation.
    # returns prime numbers <= ub.
    if ub < 2:
        return []
    prime = [True]*(ub+1)
    prime[0] = False
    prime[1] = False
    p = 2
    while p*p <= ub:
        if prime[p]:
            # don't need to check p+1 ~ p^2-1 (they've already been checked).
            for i in range(p*p, ub+1, p):
                prime[i] = False
        p += 1
    return prime

Q = int(input())
primes = sieve_of_eratosthenes(10**5)
cum_sum = [0]*(10**5+1)
for i in range(1, 10**5+1):
    if primes[i] and primes[(i+1) // 2]:
        cum_sum[i] = cum_sum[i-1] + 1
    else:
        cum_sum[i] = cum_sum[i-1]

for _ in range(Q):
    l, r = map(int, input().split())
    ans = cum_sum[r] - cum_sum[l-1]
    print(ans)