Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
a = list(map(int, input().split()))

cond = []
for i in range(len(a)):
    for j in range(i, len(a)):
        cond.append(sum(a[i:j+1]))

ans = 0
for i in reversed(range(40)):
    b = ans + 2**i
    cnt = 0
    for c in cond:
        if c&b==b:
            cnt += 1
    if cnt>=K:
        ans = b

print(ans)


Fixed submission:
N,K = map(int, input().split())
a = list(map(int, input().split()))

b = [0]
for ai in a:
    b.append(b[-1]+ai) 

cond = []
for i in range(N+1):
    for j in range(i+1, N+1):
        cond.append(b[j]-b[i])

ans = 0
for i in reversed(range(40)):
    b = ans + 2**i
    cnt = 0
    for c in cond:
        if c&b==b:
            cnt += 1
    if cnt>=K:
        ans = b

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
a = list(map(int, input().split()))

cond = []
for i in range(len(a)):
    for j in range(i, len(a)):
        cond.append(sum(a[i:j+1]))

ans = 0
for i in reversed(range(40)):
    b = ans + 2**i
    cnt = 0
    for c in cond:
        if c&b==b:
            cnt += 1
    if cnt>=K:
        ans = b

print(ans)

Fixed submission:
N,K = map(int, input().split())
a = list(map(int, input().split()))

b = [0]
for ai in a:
    b.append(b[-1]+ai) 

cond = []
for i in range(N+1):
    for j in range(i+1, N+1):
        cond.append(b[j]-b[i])

ans = 0
for i in reversed(range(40)):
    b = ans + 2**i
    cnt = 0
    for c in cond:
        if c&b==b:
            cnt += 1
    if cnt>=K:
        ans = b

print(ans)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = dict()
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if ans[idx]!="?":
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Fixed submission:
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = dict()
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if idx in ans.keys():
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = ["?"]*L
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if ans[idx]!="?":
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Fixed submission:
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = dict()
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if idx in ans.keys():
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt, ceil
import sys

N, M = map(int, input().split())
rootM = max(ceil(sqrt(M)), M//N)

for m in reversed(range(1, rootM+1)):
    if M % m == 0:
        # print(m)
        if M // m >= N:
            print(m)
            sys.exit()

Fixed submission:
from math import sqrt, floor
 
N, M = map(int,input().split())
 
rootM = floor(sqrt(M))
l = []
for i in range(1, rootM +1):
    if M % i == 0:
        l.append(i)
        l.append(M//i)
        
ans = 1
for li in l:
    ans = max(ans, li) if li <= M // N else ans
print(ans)

Buggy python submission (verdict: Runtime Error):
from math import sqrt, floor
import sys

N, M = map(int, input().split())
rootM = floor(sqrt(M))

for m in reversed(range(rootM)):
    if M % m == 0:
        if M // m >= N:
            print(m)
            sys.exit()

Fixed submission:
from math import sqrt, floor
 
N, M = map(int,input().split())
 
rootM = floor(sqrt(M))
l = []
for i in range(1, rootM +1):
    if M % i == 0:
        l.append(i)
        l.append(M//i)
        
ans = 1
for li in l:
    ans = max(ans, li) if li <= M // N else ans
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10**9+7
from math import factorial    
def comb(a, b):
    ret = factorial(a) // (factorial(a-b)*factorial(b))
    return ret % MOD

if __name__ == '__main__':
    N,M = map(int, input().split())
    ans = 1
    
    #  素因数分解
    i=2
    nokori = M
    while i*i <= nokori:
        if nokori%i==0:
            cnt = 0
            while nokori%i==0:
                cnt += 1
                nokori //= i
            ans *= comb(N+cnt-1, N-1)
            ans %= MOD
        i += 1
            
    if nokori != 1:
        ans *= comb(N+1-1, N-1)
        ans %= MOD
        
    print(ans)


Fixed submission:
MOD = 10**9+7

def modpow(a:int, p:int)->int:
    # return a**p (mod MOD)
    if p==0: return 1
    if p%2==0:
        half_p = p//2
        half = modpow(a, half_p)
        return half*half % MOD
    else:
        return a * modpow(a, p-1) % MOD
    
def comb(a:int, b:int):
    if b > a-b: return comb(a, a-b)
    mul = 1
    div = 1
    for i in range(b):
        mul *= a-i
        div *= i+1
        mul %= MOD
        div %= MOD
        
    ret = mul * modpow(div, MOD-2) % MOD
    return ret

if __name__ == '__main__':
    N,M = map(int, input().split())
    ans = 1
    
    #  素因数分解
    i=2
    nokori = M
    while i*i <= nokori:
        if nokori%i==0:
            cnt = 0
            while nokori%i==0:
                cnt += 1
                nokori //= i
            ans *= comb(N+cnt-1, N-1)
            ans %= MOD
        i += 1
            
    if nokori != 1:
        ans *= comb(N+1-1, N-1)
        ans %= MOD
        
    print(ans)
Buggy python submission (verdict: Runtime Error):
from math import gcd
n, X = map(int, input().split())
x = list(map(int, input().split()))

ans = abs(x[0]-X)
for xi in x:
    ans = gcd(ans, abs(xi-X))
    
print(ans)

Fixed submission:
# from math import gcd # ダメ
def gcd(a,b): 
    while b!=0:
        a,b=b,a%b
    return a

n, X = map(int, input().split())
x = list(map(int, input().split()))

ans = abs(x[0]-X)
for xi in x:
    ans = gcd(ans, abs(xi-X))
    
print(ans)
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())

ks = [x for x in range(1, n+1) if x % k == 0]
k2s = [x for x in range(1, n+1) if x % (k//2) == 0 and x % k != 0] 

if k % 2 == 0: # if even
    print(len(ks) ** 3 + len(k2s) ** 3)
else:
    print(len(ks) ** 3)

Fixed submission:
n, k = map(int, input().split())

ks = [x for x in range(1, n+1) if x % k == 0]

if k % 2 == 0: # if even
    k2s = [x for x in range(1, n+1) if x % (k//2) == 0 and x % k != 0] 
    print(len(ks) ** 3 + len(k2s) ** 3)
else:
    print(len(ks) ** 3)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())

ks = [x for x in range(1, n+1) if x % k == 0]
k2s = [x for x in range(1, n+1) if x % (k//2) == 0]

if k % 2 == 0: # if even
    print(len(k2s))
else:
    print(len(ks))

Fixed submission:
n, k = map(int, input().split())

ks = [x for x in range(1, n+1) if x % k == 0]

if k % 2 == 0: # if even
    k2s = [x for x in range(1, n+1) if x % (k//2) == 0 and x % k != 0] 
    print(len(ks) ** 3 + len(k2s) ** 3)
else:
    print(len(ks) ** 3)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())

if max(a, b) > 8:
    print(':(')
else:
    print('Yay!')

Fixed submission:
a,b = map(int, input().split())

if max(a, b) > 8:
    print(':(')
else:
    print('Yay!')

Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())

if max(a, b) > 8:
    print(':(')
else:
    print('Yay!')

Fixed submission:
a,b = map(int, input().split())

if max(a, b) > 8:
    print(':(')
else:
    print('Yay!')
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
xyz = [tuple(map(int, input().split())) for _ in range(N)]
xs,ys,zs= zip(*xyz)

def calc(t):
    x,y,z = zip(*t)
    return abs(sum(x)) + abs(sum(y)) + abs(sum(z))

cond = []
sx = sorted(xyz, key=lambda x:x[0])
cond.append(calc(sx[:M]))
cond.append(calc(sx[-M:]))
sy = sorted(xyz, key=lambda x:x[1])
cond.append(calc(sy[:M]))
cond.append(calc(sy[-M:]))
sz = sorted(xyz, key=lambda x:x[2])
cond.append(calc(sz[:M]))
cond.append(calc(sz[-M:]))

print(max(cond))

Fixed submission:
N,M = map(int, input().split())
xyz = [tuple(map(int, input().split())) for _ in range(N)]

constraint = []
for x,y,z in xyz:
    ci = []
    for b in range(8):
        v = 0
        if (b>>0)&1==1: v += x 
        else: v -= x
        if (b>>1)&1==1: v += y
        else: v -= y
        if (b>>2)&1==1: v += z 
        else: v -= z
        ci.append(v)
    #print(ci)
    constraint.append(ci)

ans = 0
for c in zip(*constraint):
    cond = sorted(c, reverse=True)[:M]
    ans = max(ans, sum(cond))
print(ans)
Buggy python submission (verdict: Runtime Error):
N,C = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(int, input().split())) for _ in range(N)]

mod3 = {0:[], 1:[], 2:[]}
for i in range(N):
    for j in range(N):
        m = (i+j)%3
        mod3[m].append(color[i][j])
        
from collections import Counter
from itertools import combinations, permutations
cnts = [Counter(mod3[i]) for i in range(3)]
# print(cnts)
ans = float('inf')
for comb in combinations(range(C), 3):
    for p in permutations(comb):
        cond = 0
        for i in range(3):
            for col in cnts[i].keys():
                cond += cnts[i][col]*cost[col][p[i]]
        ans = min(ans, cond)
        #print(cond, p)
print(ans)
    

Fixed submission:
N,C = map(int, input().split())
cost = [list(map(int, input().split())) for _ in range(C)]
color = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N)]

mod3 = {0:[], 1:[], 2:[]}
for i in range(N):
    for j in range(N):
        m = (i+j)%3
        mod3[m].append(color[i][j])
        
from collections import Counter
from itertools import combinations, permutations
cnts = [Counter(mod3[i]) for i in range(3)]
# print(cnts)
ans = float('inf')
for comb in combinations(range(C), 3):
    for p in permutations(comb):
        cond = 0
        for i in range(3):
            for col in cnts[i].keys():
                cond += cnts[i][col]*cost[col][p[i]]
        ans = min(ans, cond)
        #print(cond, p)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())

sums =[]
for A in range(1,int(N/2)):
    B = N-A
    a_sum = sum(list(map(int, list(str(A)))))
    b_sum = sum(list(map(int, list(str(B)))))
    sums.append(a_sum+b_sum)

print(min(sums))

Fixed submission:
N = int(input())

minsum = int(1e4)

for A in range(1,int(N/2)):
    B = N-A
    a_sum = sum(list(map(int, list(str(A)))))
    b_sum = sum(list(map(int, list(str(B)))))
    if minsum > a_sum+b_sum: minsum = a_sum+b_sum

if int(N/2)==1:
    minsum=N
print(minsum)
Buggy python submission (verdict: Time Limit Exceeded):
# n < 50 のとき
# substring の全列挙

s = input()
n = len(s)
K = int(input())

substr = []
for i in range(n):
    for j in range(i, n):
        substr.append(s[i:j+1])

substr = sorted(list(set(substr)))
print(substr[K-1])
    

Fixed submission:
s = input()
n = len(s)
K = int(input())

substr = []
# O(n*K)
for i in range(n):
    for j in range(i, i+K):
        substr.append(s[i:j+1])

substr = sorted(list(set(substr)))
print(substr[K-1])
Buggy python submission (verdict: Runtime Error):
H, W = map(int, input().split())

inpt =[]
for h in H:
    i = str(input())
    inpt.append(i)

string = 'No'

for h in range(H):
    for w in range(W):
        if h == H-1 or w == W-1:
            continue
        if inpt[h][w] == '#':
            if inpt[h+1][w] == '#' or inpt[h][w+1] == '#':
                 string = 'Yes'
                 
print(string)


Fixed submission:
a, b = map(int, input().split())
takahashi = 0
 
for x in range(1, a):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(1, b+1):
    if x == a:
        takahashi += 1
print(takahashi)

Buggy python submission (verdict: Runtime Error):

H, W = map(int, input().split())

inpt =[]
for h in H:
    i = str(input())

string = 'No'

for h in range(H):
    for w in range(W):
        if h == H-1 or w == W-1:
            continue
        if inpt[h][w] == '#':
            if inpt[h+1][w] == '#' or inpt[h][w+1] == '#':
                 string = 'Yes'
                 
print(string)

Fixed submission:
a, b = map(int, input().split())
takahashi = 0
 
for x in range(1, a):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(1, b+1):
    if x == a:
        takahashi += 1
print(takahashi)

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


takahashi = 0
 
# till last month
for x in range(1, a-1):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(i, b+1):
    if x == a:
        takahashi += 1
print(takahashi)

Fixed submission:
a, b = map(int, input().split())
takahashi = 0
 
for x in range(1, a):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(1, b+1):
    if x == a:
        takahashi += 1
print(takahashi)

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

a, b = 12, 10


takahashi = 0
 
# till last month
for x in range(1, a-1):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(i, b+1):
    if x == a:
        takahashi += 1
print(takahashi)

Fixed submission:
a, b = map(int, input().split())
takahashi = 0
 
for x in range(1, a):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(1, b+1):
    if x == a:
        takahashi += 1
print(takahashi)

Buggy python submission (verdict: Runtime Error):
a, b = int (input())
takahashi = 0

for x in range(1, a+1):
    for y in range(1, b+1):
        if x == y:
            takahashi += 1

print(takahashi)
        

Fixed submission:
a, b = map(int, input().split())
takahashi = 0
 
for x in range(1, a):
    for y in range(1, 31):
        if x == y:
            takahashi += 1
 
for x in range(1, b+1):
    if x == a:
        takahashi += 1
print(takahashi)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
primes = set([2])
for i in range(3, 55555+1):
    for p in primes:
        if i%p==0: break
    else:
        primes.add(i)

from itertools import combinations
p_list = sorted(list(primes))
for c in combinations(p_list, N):
    ok = True
    for c5 in combinations(c, 5):
        if sum(c5) in primes:
            ok = False
    if ok:
        print(*c)
        break

Fixed submission:
N = int(input())
primes = set([2])
mod5_1 = []
for i in range(3, 55555+1):
    if len(mod5_1)==N: 
        break
    for p in primes:
        if i%p==0: 
            break
    else:
        primes.add(i)
        if i%5==1:
            mod5_1.append(i)
            
print(*mod5_1)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))

ruiseki = [0]
for ai in a:
    ruiseki.append(ruiseki[-1] + ai)

d = defaultdict(lambda:0)
for ri in ruiseki:
    d[ri] += 1

def comb_fermat(n:int, r:int)->int:
    # Fermat's little theorem: O(r)
    # return nCr
    if r > n: return 0
    if r > n-r: return comb_fermat(n, n-r)
    mul,div = 1,1
    for i in range(r):
        mul *= n-i
        div *= i+1

    ret = mul * pow(div, MOD-2)
    return ret

ans = 0
for k in d.keys():
    ans += comb_fermat(d[k], 2)
print(ans)


Fixed submission:
# a 200
from collections import Counter
from math import factorial

N = int(input())
a = list(map(int, input().split()))

#累計和
wa = [0]
for ai in a:
    wa.append(wa[-1]+ai)
wa = wa[1:]

def combination(n, r):
    return factorial(n)//(factorial(r)*factorial(n-r))

c = Counter(wa)
ans = 0

for k,v in c.items():
    if v<2: continue
    ans += combination(v, 2)
    
ans += c[0]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0,1)]) # y,x,step
visited = [[False]*W for _ in range(H)]
visited[0][0] = True

while q:
    y,x,step = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - step)
        break
    visited[y][x] = True
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        if not(0<=y+dy<H and 0<=x+dx<W):
            continue
        if visited[y+dy][x+dx] or maze[y+dy][x+dx]=="#":
            continue
        q.append((y+dy, x+dx, step+1))
else:
    print(-1)

Fixed submission:
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0)])
dist = [[float('inf')]*W for _ in range(H)]
dist[0][0] = 1

while q:
    y,x = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - dist[y][x])
        break
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        nx,ny = x+dx, y+dy
        if not(0<=ny<H and 0<=nx<W):
            continue
        if maze[ny][nx]=="." and dist[ny][nx]==float('inf'):
            q.append((ny, nx))
            dist[ny][nx] = dist[y][x] + 1
else:
    print(-1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0,1)]) # y,x,step
visited = [[False]*W for _ in range(H)]
visited[0][0] = True

while q:
    y,x,step = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - step)
        break
    visited[y][x] = True
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        if not(0<=y+dy<H and 0<=x+dx<W):
            continue
        if visited[y+dy][x+dx] or maze[y+dy][x+dx]=="#":
            continue
        q.append((y+dy, x+dx, step+1))
else:
    print(-1)

Fixed submission:
from collections import deque
H,W = map(int, input().split())
maze = [input() for _ in range(H)]
cnt_wall = 0
for y in range(H):
    for x in range(W):
        if maze[y][x]=="#":
            cnt_wall += 1
            
q = deque([(0,0)])
dist = [[float('inf')]*W for _ in range(H)]
dist[0][0] = 1

while q:
    y,x = q.popleft()
    #print(y,x,step)
    if (y,x)==(H-1,W-1):
        print(H*W - cnt_wall - dist[y][x])
        break
    for dy,dx in zip([0,0,1,-1], [1,-1,0,0]):
        nx,ny = x+dx, y+dy
        if not(0<=ny<H and 0<=nx<W):
            continue
        if maze[ny][nx]=="." and dist[ny][nx]==float('inf'):
            q.append((ny, nx))
            dist[ny][nx] = dist[y][x] + 1
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
c = int(input())
x = int(input())

cnt = 0
for c500 in range(a+1):
    for c100 in range(b+1):
        for c50 in range(c+1):
            if c500*500 + c100*100 + c50*50 == x:
                cnt += 1
        
print(cnt)

Fixed submission:
x = int(input())
a = int(input())
b = int(input())
print((x-a)%b)
Buggy python submission (verdict: Runtime Error):
a,b = map(int, input().split())
s = input()

try:
    if '-' not in s: raise 
    sa, sb = map(int, s.split('-'))
#     print(sa, sb)
    if len(sa)==a and len(sb)==b:
        print('Yes')
except ValueError:
    print('No')

Fixed submission:
import re

a,b = map(int, input().split())
s = input()

regex = '[0-9]{%d}-[0-9]{%d}' %(a,b)
print('Yes' if re.match(regex, s) else 'No')
Buggy python submission (verdict: Runtime Error):
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(N+2)
for i in range(1, N+2):
    cnt[i] += cnt[i-1]
    if is_prime[i] and is_prime[(i+1)//2]:
        cnt[i] += 1
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Fixed submission:
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(int(1e5)+2)
for p in primes:
    if (p+1)//2 in primes:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
# D
prime_num = set([2])
size = int(1e5)*2+1
for i in range(3,size,2):
    for p in prime_num:
        if i%p==0: break
        else: continue
    else:
        prime_num.add(i)

cnt = [0]*(int(1e5)+2)
for p in prime_num:
    if p<=int(1e5) and (p+1)//2 in prime_num:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l])

Fixed submission:
# D
N = 10**5
primes = set([])
is_prime = [True]*(N+1)
is_prime[0] = False
is_prime[1] = False
for i in range(2, N+1):
    if is_prime[i]:
        primes.add(i)
        for j in range(2, N//i+1):
            is_prime[j*i] = False
    
# like-2017
cnt = [0]*(int(1e5)+2)
for p in primes:
    if (p+1)//2 in primes:
        cnt[p] = 1
for i in range(1, int(1e5)+2):
    cnt[i] += cnt[i-1]
#print(cnt[:100])
    
Q = int(input())
for _ in range(Q):
    l,r = map(int, input().split())
    print(cnt[r]-cnt[l-1])
Buggy python submission (verdict: Runtime Error):
x,y = map(int, input().split())

a = x # A[i]
for i in range(1,y):
            
    if (i==1 and a<=y) or a*2 <= y: 
        a *= 2 # A[i+1]
        continue
    else: break

print(i)

Fixed submission:
x,y = map(int, input().split())

a = x # A[i]
for i in range(1,70):
            
    if (i==1 and a<y) or a*2 <= y: 
        a *= 2 # A[i+1]
        continue
    else: break

print(i)
Buggy python submission (verdict: Runtime Error):
# D
N,C = map(int, input().split())
T_MAX = int(1e5)
t = [0]*(T_MAX+1)
for _ in range(N):
    si,ti,ci = map(int, input().split())
    t[si-1] += 1
    t[ti+1] -= 1
ans = 1
wa = 0
for ti in t:
    wa += ti
    ans = max(ans, wa)
print(ans)
    

Fixed submission:
# D
N,C = map(int, input().split())
st = [[] for _ in range(C)]
for _ in range(N):
    si,ti,ci = map(int, input().split())
    st[ci-1].append((si,ti))
    
T_MAX = int(1e5)
imos = [0]*(T_MAX+1)
for ch in range(C):
    if st[ch]==[]: continue
    st[ch].sort()
    prev_s, prev_t = st[ch][0]
    for si,ti in st[ch][1:]:
        if si!=prev_t:
            imos[prev_s-1] += 1
            imos[prev_t] -= 1
        else:
            imos[prev_s-1] += 1
            imos[prev_t-1] -= 1
        prev_s,prev_t = si,ti
    else:
        imos[prev_s-1] += 1
        imos[prev_t] -= 1
# print(imos)
ans = 1
wa = 0
for imosi in imos:
    wa += imosi
    ans = max(ans, wa)
print(ans)