Buggy python submission (verdict: Time Limit Exceeded):
def erastotenes(n):
    prime=[2]
    limit=int(n**0.5)
    data=[i+1 for i in range(2, n, 2)]      #奇数のリストを作成
    while True:
        p=data[0]
        if p>=limit:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]


naturals=erastotenes(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

Fixed submission:
def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(ruiseki[right]-ruiseki[left-1])

Buggy python submission (verdict: Time Limit Exceeded):
def sieve(n):
    tmp=[i for i in range(n, 1, -1)]
    s=[]
    while len(tmp)>0:
        p=tmp.pop()
        s.append(p)
        for i in range(len(tmp), 0, -1):
            if tmp[-i]%p==0:
                del tmp[-i]
    return s

naturals=sieve(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

Fixed submission:
def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(ruiseki[right]-ruiseki[left-1])

Buggy python submission (verdict: Time Limit Exceeded):
def sieve(n):
    tmp=[i for i in range(n, 1, -1)]
    s=[]
    while len(tmp)>0:
        p=tmp.pop()
        s.append(p)
        for i in range(len(tmp), 0, -1):
            if tmp[-i]%p==0:
                del tmp[-i]
    return s

naturals=sieve(100000)

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    count=0
    for i in range(left, right+1):
        if i==1 or i%2==0:
            continue
        if i in naturals and int((i+1)/2) in naturals:
            count+=1
    print(count)

Fixed submission:
def get_isPrime(n):         #1~nまでの数で、素数は1、それ以外は0となるようなリストを返す
    isprime=[1]*(n+1)
    isprime[0]=0
    isprime[1]=0
    for i in range(2, int(n**0.5)+1):
        if not isprime[i]:
            continue
        for j in range(i*2, n+1, i):
            isprime[j]=0
    return isprime

max_n=100000
isprime=get_isPrime(max_n)

ruiseki=[]
for i in range(max_n+1):
    if i==0 or i==1 or i==2:
        ruiseki.append(0)
    else:
        if i%2==0:
            ruiseki.append(ruiseki[i-1])
        else:
            if isprime[i] and isprime[int((i+1)/2)]:
                ruiseki.append(ruiseki[i-1]+1)
            else:
                ruiseki.append(ruiseki[i-1])

q=int(input())
for _ in range(q):
    left, right=map(int,input().split())
    print(ruiseki[right]-ruiseki[left-1])