Buggy python submission (verdict: Time Limit Exceeded):
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	if i==j:
		if C[i]>0:
			print 1
		else:
			print 0
	else:
		if i==min(C.keys()):
			print C[j]
		else:
			print C[j]-C[i-1]
		

Fixed submission:
N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

prime=[i for i in range(0, max_n+1)]
prime[1]=0
p_len=len(prime)
for i in range(2,p_len):
	if prime[i]!=0:
		for j in range (i+i,p_len,i):
			prime[j]=0
#print prime

C=[0 for i in range(max_n+1)]
cnt=0
for i in range(max_n+1):
	if prime[i]!=0 and prime[(i+1)/2]!=0:
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt

#print C


for i,j in a:
	print C[j]-C[i-1]

Buggy python submission (verdict: Time Limit Exceeded):
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

#print min_n,max_n
#print a

C={}
cnt=0
for i in range(min_n, max_n+1):
	if is_prime(i) and is_prime( (i+1)/2 ):
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt
#print C

for i,j in a:
	if i==j:
		if C[i]>0:
			print 1
		else:
			print 0
	else:
		if i==min(C.keys()):
			print C[j]
		else:
			print C[j]-C[i-1]
		

Fixed submission:
N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

prime=[i for i in range(0, max_n+1)]
prime[1]=0
p_len=len(prime)
for i in range(2,p_len):
	if prime[i]!=0:
		for j in range (i+i,p_len,i):
			prime[j]=0
#print prime

C=[0 for i in range(max_n+1)]
cnt=0
for i in range(max_n+1):
	if prime[i]!=0 and prime[(i+1)/2]!=0:
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt

#print C


for i,j in a:
	print C[j]-C[i-1]

Buggy python submission (verdict: Time Limit Exceeded):
def is_prime(q):
    q = abs(q)
    if q == 2: return True
    if q < 2 or q&1 == 0: return False
    return pow(2, q-1, q) == 1


N=input()
l=[ map(int,raw_input().split()) for i in range(N)]

a=[]
for m in l:
	cnt=0
	for i in range(m[0],m[1]+1):
		if i%2==0:
			continue
		elif i%3==0 and i!=3:
			continue
		else:
			if is_prime(i) and is_prime( (i+1)/2 ):
				cnt+=1
	a.append(cnt)


for i in a:
	print i
		

Fixed submission:
N=input()
min_n=float("inf")
max_n=float("-inf")
a=[]
for i in range(N):
	l,r=map(int,raw_input().split())
	a.append((l,r))
	min_n=min(min_n,l)
	max_n=max(max_n,r)

prime=[i for i in range(0, max_n+1)]
prime[1]=0
p_len=len(prime)
for i in range(2,p_len):
	if prime[i]!=0:
		for j in range (i+i,p_len,i):
			prime[j]=0
#print prime

C=[0 for i in range(max_n+1)]
cnt=0
for i in range(max_n+1):
	if prime[i]!=0 and prime[(i+1)/2]!=0:
		cnt+=1
		C[i]=cnt
	else:
		C[i]=cnt

#print C


for i,j in a:
	print C[j]-C[i-1]