Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
x=int(input())
List=[int(input()) for i in range (x)]
sorted(List)
print(List)

Fixed submission:
x=int(input())
List=[input() for i in range (x)]
List=sorted(List)
sum=-1
count=1
ans=[]
for i in range (x-1):
    if List[i] == List[i+1]:
        count+=1
    elif sum>count:
        count=1
    elif sum==count:
        count=1
        ans+=[List[i]]
    else:
        sum=count
        count=1
        ans=[]
        ans+=[List[i]]
if sum==count:
    ans+=[List[-1]]
elif sum<count:
        sum=count
        count=1
        ans=[]
        ans+=[List[i]]
ans=sorted(ans)
for i in ans:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
a,b=map(int,input().split())
List=list(map(int,input().split()))
t=-1
for i in range(a-b+1):
    if sum(List[i:i+b]) >t:
        t=sum(List[i:i+b])
print((t+b)/2)

Fixed submission:
a,b=map(int,input().split())
List=list(map(int,input().split()))
t=-1
S=[0]
for i in range(a):
    S+=[S[i]+List[i]]
t=-1
for i in range(a-b+1):
    if S[i+b]-S[i]>t:
        t=S[i+b]-S[i]
print((t+b)/2)
Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
print(mayh.ceil(a/b))

Fixed submission:
import math
a,b=map(int,input().split())
print(math.ceil(a/b))
Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
print(math.gcd(a,b))

Fixed submission:
a,b=map(int,input().split())
i=min(a,b)
j=max(a,b)
while not(i==0) and not(j==0):
  x=i
  i=j%i
  j=x
print(int(a*b/j))
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
s=sum(a,b,c)
if s>=22:
  print("bust")
else:
  print("win")

Fixed submission:
a,b,c=map(int,input().split())
s=a+b+c
if s>=22:
  print("bust")
else:
  print("win")
Buggy python submission (verdict: Runtime Error):
a=input()
if a=="SUN":
  print(7)
if a=="MON":
  print(6)
if a=="TUE":
  print(5)
if a=="WED":
  print(4)
if a=="THU":
  print(3)
if a=="FRI":
  print(2)
if a=="SAT"
  print(1)

Fixed submission:
a=input()
if a=="SUN":
  print(7)
if a=="MON":
  print(6)
if a=="TUE":
  print(5)
if a=="WED":
  print(4)
if a=="THU":
  print(3)
if a=="FRI":
  print(2)
if a=="SAT":
  print(1)

Buggy python submission (verdict: Runtime Error):
a=input()
if a==SUN:
  print(7)
if a==MON:
  print(6)
if a==TUE:
  print(5)
if a==WED:
  print(4)
if a==THU:
  print(3)
if a==FRI:
  print(2)
if a==SAT
  print(1)

Fixed submission:
a=input()
if a=="SUN":
  print(7)
if a=="MON":
  print(6)
if a=="TUE":
  print(5)
if a=="WED":
  print(4)
if a=="THU":
  print(3)
if a=="FRI":
  print(2)
if a=="SAT":
  print(1)
Buggy python submission (verdict: Runtime Error):
a=int(input())
s=input()
for i in range(a):
  d=List[i]+a
  if d>=91:
    d-=26
  print(d,end="")

Fixed submission:
a=int(input())
s=input()
for i in range(len(s)):
  d=ord(s[i])+a
  if d>=91:
    d-=26
  print(chr(d),end="")
Buggy python submission (verdict: Time Limit Exceeded):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
s=list(combinations(l,3))
ans=0
for i,j,k in s:
  if i+j>k:
    ans+=1
print(ans)

Fixed submission:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a=ii()
l=list(mi())
l=sorted(l)
ans=0
for i in range(a-2):
  for j in range(i+1,a-1):
    s=bisect.bisect_left(l,l[i]+l[j])
    ans+=s-j-1
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
s=i()
for i in range(math.ceil(s/2)):
  if not s[i]=="R" or s[i]=="U" or s[i]=="D":
    print("No")
    sys.exit()
for j in range(s//2):
  if not s[i]=="L" or s[i]=="U" or s[i]=="D":
    print("No")
print('Yes')

Fixed submission:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
s=i()
for i in range(math.ceil(len(s)/2)):
  if not (s[2*i]=="R" or s[2*i]=="U" or s[2*i]=="D"):
    print("No")
    sys.exit()
for j in range(len(s)//2):
  if not (s[2*j+1]=="L" or s[2*j+1]=="U" or s[2*j+1]=="D"):
    print("No")
    sys.exit()
print('Yes')
Buggy python submission (verdict: Runtime Error):
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b,c=mi()
l=[0]*a
for i in range(c):
  j=ii()
  l[i-1]+=1
for k in l:
  if b+k-c>0:
    print("Yes")
  else:
    print("No")

Fixed submission:
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b,c=mi()
l=[0]*a
for i in range(c):
  j=ii()
  l[j-1]+=1
for k in l:
  if b+k-c>0:
    print("Yes")
  else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
a,b=map(int,input().split())
List=[]
q=deque([[0,0]])
for i in range(a):
  l=list(input())
  for _ in range(b):
    if l[_]=="#":
      q.append([i,_])
      l[_]=0
  List.append(l)
q.popleft()
aaa=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while q:
  h,w=q.popleft()
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
        if List[h+x][w+y]>ans:
          ans=List[h+x][w+y]
print(ans)

Fixed submission:
from collections import deque
a,b=map(int,input().split())
List=[]
q=deque([[0,0]])
for i in range(a):
  l=list(input())
  for _ in range(b):
    if l[_]=="#":
      q.append([i,_])
      l[_]=0
  List.append(l)
q.popleft()
aaa=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while q:
  h,w=q.popleft()
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
        if List[h+x][w+y]>ans:
          ans=List[h+x][w+y]
print(ans)
Buggy python submission (verdict: Runtime Error):
c = input()
print("A" if c == "T" else "T" if c == "A" else "C" if c == "G" else "G" if c == "G")

Fixed submission:
c = input()
print("A" if c == "T" else "T" if c == "A" else "C" if c == "G" else "G")
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
dp=[0]*a
dp[0]=0
for i in range(1,a):
    dp[i]=min(abs(l[i]-l[i-j-1])+dp[i-j-1] for j in range(min(i,b)))
print(dp[-1])

Fixed submission:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
dp=[sys.maxsize]*a
dp[0]=0
for i in range(1,a):
  for j in range(min(i,b)):
    dp[i]=min(dp[i],abs(l[i]-l[i-j-1])+dp[i-j-1])
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
dp=[sys.maxsize]*a
dp[0]=0
for i in range(1,a):
  for j in range(min(i,b)):
    dp[i]=min(dp[i],abs(l[i]-l[i-j-1])+dp[i-j-1])
print(dp[-1])

Fixed submission:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
l=list(mi())
dp=[sys.maxsize]*a
dp[0]=0
for i in range(1,a):
  for j in range(min(i,b)):
    dp[i]=min(dp[i],abs(l[i]-l[i-j-1])+dp[i-j-1])
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
import numpy as np
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))

Fixed submission:
mod=10**9+7
import math
import sys
from collections import deque
import heapq
import copy
import itertools
from itertools import permutations
from itertools import combinations
import bisect
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
def i() : return sys.stdin.readline().rstrip()
a,b=mi()
dp=[0]*(b+1)
for i in range(a):
  x,y=mi()
  for i in range(b-x,-1,-1):
      dp[i+x]=max(dp[i]+y,dp[i+x])
print(max(dp))
Buggy python submission (verdict: Runtime Error):
s = input()
print(s.replace("9","c").replace("1","9").replace("c"."1"))


Fixed submission:
s = input()
print(s.replace("9","c").replace("1","9").replace("c","1"))
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
print(a*b-a-b+1)

Fixed submission:
a,b=input().split()
print((int(a)-1)*(int(b)-1))
Buggy python submission (verdict: Runtime Error):
int n = input()
print("ABC" if n < 1000 else "ABD")

Fixed submission:
n = int(input())
print("ABC" if n<1000 else "ABD")
Buggy python submission (verdict: Runtime Error):
from collections import deque
a,b=map(int,input().split())
List=[]
sumup=0
for i in range(a):
  l=list(input())
  p=l.count(".")
  sumup+=p
  List.append(l)
List[0][0]=1
q=deque([[0,0]])
while List[a-1][b-1]==".":
  h,w=q.popleft()
  aaa=[[0,1],[0,-1],[1,0],[-1,0]]
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
print(sumup-List[a-1][b-1])

Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(10000)
a,b=map(int,input().split())
List=[]
sumup=0
for i in range(a):
  l=list(input())
  p=l.count(".")
  sumup+=p
  List.append(l)
List[0][0]=1
q=deque([[0,0]])
while q:
  h,w=q.popleft()
  aaa=[[0,1],[0,-1],[1,0],[-1,0]]
  for x,y in aaa:
    if 0<=h+x<a and 0<=w+y<b:
      if List[h+x][w+y]==".":
        List[h+x][w+y]=List[h][w]+1
        q.append([h+x,w+y])
if List[a-1][b-1]==".":
  print(-1)
else:  
  print(sumup-List[a-1][b-1])
Buggy python submission (verdict: Runtime Error):
import math
map(int,input().split())
print(math.ceil((a+b)/2))

Fixed submission:
import math
a,b=map(int,input().split())
print(math.ceil((a+b)/2))
Buggy python submission (verdict: Runtime Error):
a,b,c = int(map(input().split()))
if a == b:
    print(c)
elif a == c:
    print(b)
else:
    print(a)

Fixed submission:
a,b,c = map(int,input().split())
if a == b:
    print(c)
elif a == c:
    print(b)
else:
    print(a)
Buggy python submission (verdict: Runtime Error):
n = input()
if "9" in n:
    print("Yes")
else:
    print(No)

Fixed submission:
n = input()
if "9" in n:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
a,b,c = input().split()
print("YES" if a[-1] == b[0] && b[-1] == c[0] else "NO")

Fixed submission:
a,b,c = input().split()
print("YES" if a[-1] == b[0] and b[-1] == c[0] else "NO")
Buggy python submission (verdict: Runtime Error):
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,input().split())
def i() : return int(input())
from scipy.special import perm #print(perm(4,2,exact=True))=4P2=3
a,b=mi()
ans=0
l=[[] for _ in range(a)]
for i in range(b):
  u,v=mi()
  l[u-1].append(v-1)
  l[v-1].append(u-1)
S=[]
for i in range(1,a):
  S.append(i)
lst=list(itertools.permutations(S))
for i in lst:
  x=0
  t=True
  for w in range(len(i)):
    if not i[w] in l[x]:
      t=False
      break
    x=i[w]
  if t:
    ans+=1
print(ans)

Fixed submission:
import itertools
a,b=map(int,input().split())
A=[]
for _ in range(a-1):
  A.append(_+2)
List=[list(map(int,input().split())) for i in range(b)]
count=0
for i in itertools.permutations(A):
  ju=True
  if [1,i[0]] in List or [i[0],1] in List:
    ju=True
  else:
    ju=False
  for j in range(a-2):
    if not([i[j],i[j+1]] in List) and not([i[j+1],i[j]] in List):
      ju=False
  if ju:
    count+=1
print(count)

Buggy python submission (verdict: Runtime Error):
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,input().split())
def i() : return int(input())
from scipy.special import perm #print(perm(4,2,exact=True))=4P2=3
a,b=mi()
ans=0
l=[[] for _ in range(a)]
for i in range(b):
  u,v=mi()
  l[u-1].append(v-1)
  l[v-1].append(u-1)
S=[]
for i in range(1,a):
  S.append(i)
lst=list(permutations(S))
for i in lst:
  x=0
  t=True
  for w in range(len(i)):
    if not i[w] in l[x]:
      t=False
      break
    x=i[w]
  if t:
    ans+=1
print(ans)

Fixed submission:
import itertools
a,b=map(int,input().split())
A=[]
for _ in range(a-1):
  A.append(_+2)
List=[list(map(int,input().split())) for i in range(b)]
count=0
for i in itertools.permutations(A):
  ju=True
  if [1,i[0]] in List or [i[0],1] in List:
    ju=True
  else:
    ju=False
  for j in range(a-2):
    if not([i[j],i[j+1]] in List) and not([i[j+1],i[j]] in List):
      ju=False
  if ju:
    count+=1
print(count)
Buggy python submission (verdict: Runtime Error):
a,b,c = input()split(',')
print(a,b,c)

Fixed submission:
a,b,c = input().split(',')
print(a,b,c)

Buggy python submission (verdict: Runtime Error):
a,b,c = input().split(,)
print(a,b,c)

Fixed submission:
a,b,c = input().split(',')
print(a,b,c)
Buggy python submission (verdict: Time Limit Exceeded):
a,b=map(int,input().split())
c=0
for l in range(a+1):
    for m in range(l,a+1):
        for r in range(m,a+1):
            if l+m+r==b:
                if l==m and m==r:
                    c+=1
                elif l==m:
                    c+=3
                elif m==r:
                    c+=3
                else:
                    c+=6
print(c)

Fixed submission:
a,b=map(int,input().split())
c=0
for l in range(a+1):
    for m in range(l,a+1):
        r=b-l-m
        if r >a:
            continue
        elif r<m:
            continue
        elif r==l==m:
            c+=1
        elif r==m:
            c+=3
        elif m==l:
            c+=3
        else:
            c+=6
print(c)
Buggy python submission (verdict: Time Limit Exceeded):
n, a = input(), set(map(int, raw_input().split()))
out = []
for i in a:
    for j in xrange(i / 2, -1, -1):
        if j in a:
            out.append((i, j))
            break
        elif i - j in a:
            out.append((i, i - j))
            break
print ' '.join(map(str, sorted(out, key = lambda x: x[0], reverse = True)[0]))


Fixed submission:
def check(a, b, target):
    if abs(target - a) < abs(target - b):
        return a
    else:
        return b


n, a = int(input()), list(map(int, input().split()))
if n == 2:
    a.sort(reverse = True)
    print(a[0], a[1])
    exit()
a.sort()
l, r = 0, n
target = a[-1] >> 1
while l < r:
    mid = (l + r) >> 1
    if a[mid] > target:
        r = mid
    else:
        l = mid + 1
if a[l] <= target:  # check a[l] and a[l + 1]
    print(a[-1], check(a[l], a[l + 1], target))
else:  # check a[l] and [l - 1]
    print(a[-1], check(a[l - 1], a[l], target))
Buggy python submission (verdict: Runtime Error):
a, b = map(lambda x: int(x) - 1, raw_input().split())
x = [['.'] * 100 for _ in xrange(100)]
for i in xrange(50, 100):
    for j in xrange(100):
        x[i][j] = '#'
for i in xrange(0, 50, 2):
    if b:
        for j in xrange(0, 100, 2):
            if b:
                x[i][j] = '#'
                b -= 1
for i in xrange(99, 49, -2):
    if a:
        for j in xrange(0, 100, 2):
            if a:
                x[i][j] = '.'
                a -= 1
print '\n'.join(['100 100'] + [''.join(_) for _ in x])


Fixed submission:
a, b, c, d = [input() for _ in xrange(4)]
print min(a, b) + min(c, d)
Buggy python submission (verdict: Time Limit Exceeded):
h, w, d = map(int, raw_input().split())
a = [map(int, raw_input().split()) for _ in xrange(h)]
b = {a[x][y]: (x, y) for x in xrange(h) for y in xrange(w)}
for _ in xrange(input()):
    print sum([sum([abs(b[p][i] - b[p + d][i]) for i in [0, 1]])
               for p in xrange(*(map(int, raw_input().split()) + [d]))])


Fixed submission:
h, w, d = map(int, raw_input().split())
a = [map(int, raw_input().split()) for _ in xrange(h)]
r = {a[x][y]: (x, y) for x in xrange(h) for y in xrange(w)}
b = [0] * (h * w + 1)
for _ in xrange(d + 1, h * w + 1):
    b[_] = b[_ - d] + sum([abs(r[_ - d][i] - r[_][i]) for i in [0, 1]])
for _ in xrange(input()):
    l, r = map(int, raw_input().split())
    print b[r] - b[l]
Buggy python submission (verdict: Time Limit Exceeded):
x = {}
n, m = map(int, raw_input().split())
flag = True
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    if l in x:
        if r in x:
            if x[l][1] + d != x[r][1]:
                if x[l][0] == x[r][0]:
                    flag = False
                else:
                    for k, v in x.iteritems():
                        if v[0] == r:
                            x[k] = (x[l][0], v[1] + x[l][1] + d)
        else:
            x[r] = (x[l][0], x[l][1] + d)
    else:
        x[l], x[r] = (l, 0), (l, d)
print 'Yes' if flag else 'No'


Fixed submission:
from collections import deque
n, m = map(int, raw_input().split())
graph = {_: set() for _ in xrange(n + 1)}
in_deg, dist = [0] * (n + 1), [-1] * (n + 1)
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    graph[l].add((r, d))
    in_deg[r] += 1
que = deque([i for i in xrange(n + 1) if not in_deg[i]])
cst = 1
while que:
    stp = que.popleft()  # start_point
    if in_deg[stp] < 0:
        in_deg[stp] = cst
    for v, d in graph[stp]:
        if dist[v] < 0:
            dist[v] = dist[stp] + d
        else:
            if dist[v] != dist[stp] + d:
                print 'No'
                exit()
        in_deg[v] -= 1
        if not in_deg[v]:
            que.append(v)
print 'No' if [_ for _ in in_deg[1:] if _ > 0] else 'Yes'

Buggy python submission (verdict: Runtime Error):
x = {}
n, m = map(int, raw_input().split())
if m == 0:
    print 'Yes'
    exit()
l, r, d = map(int, raw_input().split())
x[l], x[r] = 0, d
flag = True
for _ in xrange(m - 1):
    l, r, d = map(int, raw_input().split())
    if r in x:
        if x[r] != x[l] + d:
            flag = False
    else:
        x[r] = x[l] + d
print 'Yes' if flag else 'No'


Fixed submission:
from collections import deque
n, m = map(int, raw_input().split())
graph = {_: set() for _ in xrange(n + 1)}
in_deg, dist = [0] * (n + 1), [-1] * (n + 1)
for _ in xrange(m):
    l, r, d = map(int, raw_input().split())
    graph[l].add((r, d))
    in_deg[r] += 1
que = deque([i for i in xrange(n + 1) if not in_deg[i]])
cst = 1
while que:
    stp = que.popleft()  # start_point
    if in_deg[stp] < 0:
        in_deg[stp] = cst
    for v, d in graph[stp]:
        if dist[v] < 0:
            dist[v] = dist[stp] + d
        else:
            if dist[v] != dist[stp] + d:
                print 'No'
                exit()
        in_deg[v] -= 1
        if not in_deg[v]:
            que.append(v)
print 'No' if [_ for _ in in_deg[1:] if _ > 0] else 'Yes'
Buggy python submission (verdict: Runtime Error):
p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100000):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]


Fixed submission:
p = [True] * 100020
for x in xrange(2, int(100020 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100020):
            if y * x >= 100020:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100020):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]

Buggy python submission (verdict: Time Limit Exceeded):
p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
e = []
for i in xrange(100000):
    s = False
    if p[i] and p[(i + 1) / 2]:
        s = True
    e.append(s)
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print sum(e[l: r + 1])


Fixed submission:
p = [True] * 100020
for x in xrange(2, int(100020 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100020):
            if y * x >= 100020:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100020):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]

Buggy python submission (verdict: Time Limit Exceeded):
p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    for i in xrange(l, r + 1):
        if i & 1:
            if p[i] and p[(i + 1) / 2]:
                c += 1
    print c


Fixed submission:
p = [True] * 100020
for x in xrange(2, int(100020 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100020):
            if y * x >= 100020:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100020):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]