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

def eratosthenes(r):
    prime_list = [i for i in (2, 3, 5) if i <= r]

    candidates = [i for i in range(2, r+1) if i % 2 and i % 3 and i % 5]
    while len(candidates):
        prime_list.append(candidates[0])
        candidates = [i for i in candidates[1:] if i % candidates[0]]
    return prime_list

def prime_decomposition(n):
    i = 2
    table = 0
    while i * i <= n:
        while n % i == 0:
            n /= i
            table += 1
        i += 1
    if n > 1:
        table += 1
    return table

def is_prime(n):
    return prime_decomposition(n) == 1

def similer_number_2017(l, r):
    # similar_numbers = []
    # for p in eratosthenes(l, r):
    #     if is_prime(int((p+1)/2)):
    #         similar_numbers.append(p)
    # return similar_numbers
    similar_num = 0
    multi = set()
    for i in range(max(l,2), r+1):
        if i in multi:
            continue
        if is_prime(i) and is_prime((i+1)/2):
            similar_num += 1
        multi.update([x for x in range(i, r+1, i)])
    return similar_num
    

Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

for l, r in query:
    print similer_number_2017(l, r)




Fixed submission:
Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

composite_number = [False] * (100001)
for i in range(2, 100001):
    if not composite_number[i]:
        for j in range(i+i, 100001, i):
            composite_number[j] = True
    
similar_number = [0] * 100001
for i in range(3, 100001, 2):
    if not composite_number[i] and not composite_number[(i+1)/2]:
        similar_number[i] += 1

for i in range(3, 100001):
    similar_number[i] += similar_number[i-1]

for l, r in query:
    print similar_number[r] - similar_number[l-1]

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

def eratosthenes(l, r):
    prime_list = [i for i in (2, 3, 5) if i <= r]

    candidates = [i for i in range(2, r+1) if i % 2 and i % 3 and i % 5]
    while len(candidates):
        prime_list.append(candidates[0])
        candidates = [i for i in candidates[1:] if i % candidates[0]]
    return [i for i in prime_list if i >= l]

def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n /= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def is_prime(n):
    return len(prime_decomposition(n)) == 1

def similer_number_2017(l, r):
    similar_numbers = []
    for p in eratosthenes(l, r):
        if is_prime(int((p+1)/2)):
            similar_numbers.append(p)
    return similar_numbers
    

Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

for l, r in query:
    print len(similer_number_2017(l, r))




Fixed submission:
Q = int(raw_input())
query = [map(int, raw_input().split(' ')) for _ in range(Q)]

composite_number = [False] * (100001)
for i in range(2, 100001):
    if not composite_number[i]:
        for j in range(i+i, 100001, i):
            composite_number[j] = True
    
similar_number = [0] * 100001
for i in range(3, 100001, 2):
    if not composite_number[i] and not composite_number[(i+1)/2]:
        similar_number[i] += 1

for i in range(3, 100001):
    similar_number[i] += similar_number[i-1]

for l, r in query:
    print similar_number[r] - similar_number[l-1]