Buggy python submission (verdict: Time Limit Exceeded):
num = [True]*(100001)
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

for i in range(100000, 1, -1):
  if not (num[i]):
    continue
  if not (num[int((i+1)/2)]):
    num[i] = False

for i in range(int(input())):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if num[i]:
      sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
num = [True]*(100001)
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

for i in range(int(input())):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if (num[i]) and (num[int((i+1)/2)]):
      sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Runtime Error):
num = [True]*(100000)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in int(input()):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if (num[i]) and (num[int((i+1)/2)]):
      sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (num[i]) and (num[int((i+1)/2)]):
        sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Runtime Error):
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (num[i]) and (num[(i+1)/2]):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (num[i]) and (num[(i+1)/2]):
        sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  if LR[i][0] % 2 == 0:
    for i in range(LR[i][0]+1, LR[i][1]+1, 2):
      if (i in primeList) and ((i+1)/2 in primeList):
        sum = sum + 1
  else:
    for i in range(LR[i][0], LR[i][1]+1, 2):
      if (i in primeList) and ((i+1)/2 in primeList):
        sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Runtime Error):
def prime(n):
  num = [True]*n
  num[0] = num[1] = False
  for i in xrange(2,int(n**0.5)+1):
    if num[i]:
      for j in xrange(i**2, n, i):
        num[j] = False
        return [i for i in xrange(2,n) if num[i]]

Q = int(input())
LR = []
max = 0
for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

prime = prime(max)

for i in range(Q):
  sum = 0
  for num in range(LR[i][0], LR[i][1]+1):
    if (num in prime) and ((num+1) / 2 in prime):
      sum = sum + 1
  print(sum)

Q = int(input())
LR = []
max = 0
for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < int(_input[1]):
    max = int(_input[1])

prime = prime(max)

for i in range(Q):
  sum = 0
  for num in range(LR[i][0], LR[i][1]+1):
    if (num in prime) and ((num+1) / 2 in prime):
      sum = sum + 1
  print(sum)


Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])

Buggy python submission (verdict: Time Limit Exceeded):
def prime(max):
  num = [True] * (max + 1)
  n = 2
  while n ** 2 <= max:
    if num[n]:
      m = n + n
      while m <= max:
        num[m] = False
        m += n
    n += 1
  return [i for i in range(2, max + 1) if num[i]]

Q = int(input())
LR = []
max = 0
for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < int(_input[1]):
    max = int(_input[1])

prime = prime(max)

for i in range(Q):
  sum = 0
  for num in range(LR[i][0], LR[i][1]+1):
    if (num in prime) and ((num+1) / 2 in prime):
      sum = sum + 1
  print(sum)

Fixed submission:
num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

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

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])