Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def main()
    mod = 10**9+7
    N = int(input())
    a = [list(map(int, input().split())) for _ in range(N)]
    dp = [0]*(1<<N)
    dp[0] = 1
    def bitcount(i): # i < 2^32
        i = i - ((i >> 1) & 0x55555555)
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
        return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24
    for s in range(1, 1<<N):
        women = []
        m = bitcount(s)-1
        for w in range(N):
            if a[m][w] == 1 and s&1<<w:
                dp[s]+=dp[s^(1<<w)]
                dp[s]%=mod
    print(dp[-1])
main()

Fixed submission:
mod = 10**9+7
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
dp = [0]*(1<<N)
dp[0] = 1
for s in range(1, 1<<N):
    women = []
    for i in range(N):
        if (1<<i)&s:
            women.append(i)
    m = len(women)-1
    for w in women:
        if a[m][w] == 1:
            dp[s]+=dp[s^(1<<w)]
            dp[s]%=mod
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
K = input()
n = len(K)
D = int(input())
dp = [[[0]*2 for i in range(D)] for _ in range(n)]
for i in range(int(K[0])):
    dp[0][i%D][0] += 1
dp[0][int(K[0])%D][1] += 1
for i in range(n-1):
    for j in range(D):
        for d in range(10):
            dp[i+1][(j+d)%D][0]+=dp[i][j][0]
            dp[i+1][(j+d)%D][0]%=mod
        for d in range(int(K[i+1])):
            dp[i+1][(j+d)%D][0]+=dp[i][j][1]
            dp[i+1][(j+d)%D][0]%=mod
        dp[i+1][(j+int(K[i+1]))%D][1] += dp[i][j][1]
        dp[i+1][(j+int(K[i+1]))%D][1]%=mod


print(dp[-1][0][0]+dp[-1][0][1]-1)




Fixed submission:
mod = 10**9+7
K = input()
n = len(K)
D = int(input())
dp = [[[0]*2 for i in range(D)] for _ in range(n)]
for i in range(int(K[0])):
    dp[0][i%D][0] += 1
dp[0][int(K[0])%D][1] += 1
for i in range(n-1):
    for j in range(D):
        for d in range(10):
            dp[i+1][(j+d)%D][0]+=dp[i][j][0]
            dp[i+1][(j+d)%D][0]%=mod
        for d in range(int(K[i+1])):
            dp[i+1][(j+d)%D][0]+=dp[i][j][1]
            dp[i+1][(j+d)%D][0]%=mod
        dp[i+1][(j+int(K[i+1]))%D][1] += dp[i][j][1]
        dp[i+1][(j+int(K[i+1]))%D][1]%=mod
print((dp[-1][0][0]+dp[-1][0][1]-1)%mod)
Buggy python submission (verdict: Runtime Error):
import numpy as np
mod = 10**9+7
N = int(input())
s = input()
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1
for i in range(1, N):
    if s[i-1] == '>':
        dp[i][0] = dp[i-1][0]
        for j in range(1, N-i):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod
    else:
        for j in range(N-1)[::-1]:
            dp[i][j] = (dp[i][j+1]+dp[i-1][j+1])%mod
print(sum(dp[-1])%mod)

Fixed submission:
mod = 10**9+7
N = int(input())
s = input()
dp = [[0]*N for _ in range(N)]
for i in range(N):
    dp[0][i] = 1
for i in range(1, N):
    if s[i-1] == '>':
        dp[i][0] = dp[i-1][0]
        for j in range(1, N-i):
            dp[i][j] = (dp[i][j-1] + dp[i-1][j])%mod
    else:
        for j in range(N-1)[::-1]:
            dp[i][j] = (dp[i][j+1]+dp[i-1][j+1])%mod
print(sum(dp[-1])%mod)
Buggy python submission (verdict: Runtime Error):
from functools import cmp_to_key
def cmp(a, b):
    w1, s1, v1 = a
    w2, s2, v2 = b
    if min(s1, s2-w1)>min(s2, s1-w2):
        return 1
    else:
        return -1
N = int(input())
dp = [[0]*1001 for _ in range(N)]
wsv = []
for _ in range(N):
    w, s, v = map(int, input().split())
    wsv.append((w, s, v))
wsv.sort(key = cmp_to_key(cmp))
w, s, v = wsv[0]
dp[0][s] = v
for i in range(N-1):
    w, s, v = wsv[i+1]
    for j in range(1001):
        if j>=w:
            dp[i+1][min(s, j-w)] = max(dp[i][j]+v, dp[i+1][min(s, j-w)])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
print(max(dp[-1]))




Fixed submission:
from functools import cmp_to_key
def cmp(a, b):
    w1, s1, v1 = a
    w2, s2, v2 = b
    if min(s1, s2-w1)>min(s2, s1-w2):
        return 1
    else:
        return -1
N = int(input())
dp = [[0]*10001 for _ in range(N)]
wsv = []
for _ in range(N):
    w, s, v = map(int, input().split())
    wsv.append((w, s, v))
wsv.sort(key = lambda x:-(x[0]+x[1]))
w, s, v = wsv[0]
dp[0][s] = v
for i in range(N-1):
    w, s, v = wsv[i+1]
    for j in range(10001):
        if j>=w:
            dp[i+1][min(s, j-w)] = max(dp[i][j]+v, dp[i+1][min(s, j-w)])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
    dp[i+1][s] = max(dp[i+1][s], v)
print(max(dp[-1]))
Buggy python submission (verdict: Runtime Error):
a,b,k=map(int, input().split())
cnt=0
for i in range(min(a,b)+1,0,-1):
    if a%i==0 and b%i==0:
        cnt+=1
        if cnt==k:
            print(i)

Fixed submission:
n,t = map(int, input().split())
ct = [list(map(int, input().split())) for i in range(n)]
ct=sorted(ct, key=lambda cti : cti[0])
for i in range(n):
    if ct[i][1]<=t:
        print(ct[i][0])
        exit()
print('TLE')
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
v=[int(i) for i in input().split()]
v_even=[vi for vi in v[::2]]
v_odd=[vi for vi in v[1::2]]
def same(v):
    count=[]
    v_set=set(v)
    for vi in v_set:
        count.append([vi, v.count(vi)])
    count=sorted(count, key = lambda k:k[1])
    return count
e1=len(v_even)-same(v_even)[-1][1]
o1=len(v_odd)-same(v_odd)[-1][1]
e2=len(v_even)-same(v_even)[-2][1] if len(set(v_even))>1 else len(v_even)
o2=len(v_odd)-same(v_odd)[-2][1] if len(set(v_odd))>1 else len(v_odd)
if same(v_even)[-1][0]==same(v_odd)[-1][0]:
    print(min(e1+o2, e2+o1))
else:
    print(e1+o1)

Fixed submission:
from collections import Counter
n=int(input())
v=list(map(int, input().split()))
v1=Counter(v[::2])
v2=Counter(v[1::2])
c1=v1.most_common()+[(0, 0)]
c2=v2.most_common()+[(0, 0)]
if c1[0][0]==c2[0][0]:
    ans=max(c1[1][1]+c2[0][1], c1[0][1]+c2[1][1])
    print(n-ans)
else:
    print(n-c1[0][1]-c2[0][1])
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
a=[list(map(int, input().split())) for i in range(h)]
l=[]
for i in range(h):
    for j in range(w):
        if a[i][j]%2==1:
            l.append((i,j))
def move(y1,x1, y2,x2):
    if y1<y2:
        for i in range(y1,y2):
            print(i+1, x1+1, i+2, x1+1)
    elif y1>y2:
        for i in range(y1,y2, -1):
            print(i+1, x1+1, i, x1+1)
    if x1<x2:
        for i in range(x1,x2):
            print(y2+1, i+1, y2+1, i+2)
    elif x1>x2:
        for i in range(x1,x2, -1):
            print(y2+1, i+1, y2+1, i)
ans=0
for i in range(0,len(l),2):
    ans+=abs(l[i][0]-l[i+1][0])+abs(l[i][1]-l[i+1][1])
print(ans)
for i in range(0,len(l),2):
    move(l[i][0],l[i][1],l[i+1][0],l[i+1][1])

Fixed submission:
H, W = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]
ans = []
for i in range(H-1):
    for j in range(W):
        if a[i][j] % 2 == 1:
            ans.append((i+1, j+1, i+2, j+1))
            a[i+1][j]+=1
for i in range(W-1):
    if a[H-1][i] % 2 == 1:
        ans.append((H, i+1, H, i+2))
        a[H-1][i+1] +=1
print(len(ans))
for a in ans:
    print(*a)
Buggy python submission (verdict: Runtime Error):
n = int(input())
yaku=[]
ans=0
for j in range(1, n+1)[::2]:
    for i in range(1, i+1):
        if j%i==0:
            yaku.append(i)
    if len(yaku)==8:
        ans+=1
print(ans)
    

Fixed submission:
n = int(input())
yaku=[]
ans=0
for j in range(1, n+1)[::2]:
    yaku=[]
    for i in range(1, j+1):
        if j%i==0:
            yaku.append(i)
    if len(yaku)==8:
        ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
S1 = [A[0]]*N
S2 = [A[-1]]*N
def cut(S):
    s = S[-1]/2
    i = bisect_left(S, s)
    if abs(S[i]-s) < abs(S[i-1]-s):
        return (S[i], S[-1]-S[i])
    else: return (S[i-1], S[-1]-S[i-1])
for i in range(1, N):
    S1[i] = S1[i-1]+A[i]
    S2[i] = S2[i-1]+A[N-i-1]
ans = S1[-1]
for i in range(2, N-1):
    P, Q = cut(S1[:i])
    R, S = cut(S2[:N-i])
    res = max(P, Q, R, S)-min(P, Q, R, S)
    ans = min(ans, res)
print(ans)

Fixed submission:
from bisect import bisect_left
N = int(input())
A = list(map(int, input().split()))
S1 = [A[0]]*N
S2 = [A[-1]]*N
for i in range(1, N):
    S1[i] = S1[i-1]+A[i]
    S2[i] = S2[i-1]+A[N-i-1]
ans = S1[-1]
for i in range(1, N-2):
    s1 = S1[i]
    b = bisect_left(S1, s1/2)
    if abs(S1[b]-s1/2)>abs(s1/2-S1[b-1]):
        b-=1
    P, Q = S1[b], s1-S1[b]
    s2 = S2[N-i-2]
    c = bisect_left(S2, s2/2)
    if abs(S2[c]-s2/2)>abs(s2/2-S2[c-1]):
        c-=1
    R, S = S2[c], s2-S2[c]
    res = max(P, Q, R, S)-min(P, Q, R, S)
    ans = min(ans, res)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict, deque
import sys
N, M = map(int, input().split())
edges = [list(range(N)) for i in range(N)]
for i in range(N):
    edges[i].remove(i)
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].remove(b-1)
    edges[b-1].remove(a-1)
size = defaultdict(lambda: [0, 0])
color = [-1]*N
def set_color(root):
    
    que = deque([root])
    color[root] = 0
    size[root][0]+=1
    while que:
        v = que.pop()
        for nv in edges[v]:
            if color[nv]<0:
                c = 1- color[v]
                color[nv] = c
                size[root][c]+=1
                que.append(nv)
            elif color[nv] == color[v]:
                print(-1)
                sys.exit()
for i in range(N):
    if color[i]<0:
        set_color(i)
S = set([0])
for a, b in size.values():
    S = set(s+b for s in S)|set(s+a for s in S)
ans = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in S)            
print(ans)                

Fixed submission:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
edges = [list(range(N)) for i in range(N)]
for i in range(N):
    edges[i].remove(i)
for _ in range(M):
    a, b = map(int, input().split())
    edges[a-1].remove(b-1)
    edges[b-1].remove(a-1)
size = defaultdict(lambda: [0, 0])
color = [-1]*N
def set_color(root):
    
    que = deque([root])
    color[root] = 0
    size[root][0]+=1
    while que:
        v = que.pop()
        for nv in edges[v]:
            if color[nv]<0:
                c = 1- color[v]
                color[nv] = c
                size[root][c]+=1
                que.append(nv)
            elif color[nv] == color[v]:
                print(-1)
                sys.exit()
for i in range(N):
    if color[i]<0:
        set_color(i)
S = set([0])
for a, b in size.values():
    S = set(s+b for s in S)|set(s+a for s in S)
ans = min(x*(x-1)//2+(N-x)*(N-x-1)//2 for x in S)            
print(ans)
Buggy python submission (verdict: Runtime Error):
mod = 998244353
N, A, B, K = map(int, input().split())
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
ans = 0
for k in range(N+1):
    r = K-k*A
    if r%B != 0 or r//B>N:
        continue
    l = r//B
    ans+=comb(N, k)*comb(N, l)
    ans%=mod
print(ans)



Fixed submission:
mod = 998244353
N, A, B, K = map(int, input().split())
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact
fact = make_fact(N) #＠
def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv
fact_inv = make_fact_inv(N)#＠
def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
ans = 0
for k in range(N+1):
    r = K-k*A
    if r<0 or r%B != 0 or r//B>N:
        continue
    l = r//B
    ans+=comb(N, k)*comb(N, l)
    ans%=mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int, input().split()))
a=[format(i, '030b') for i in a]
cnt=0
t=-1
ans=0
cnt=[0]*30
for s in range(n):
    while True:
        if t==n-1:
            ans+=t-s+1
            break
        if all(cnt[i]+int(a[t+1][i])<=1 for i in range(30)):
            for i in range(30):
                cnt[i]+=int(a[t+1][i])
            t+=1
        else:
            ans+=(t-s+1)
            break
        
    for i in range(30):
        cnt[i]-=int(a[s][i])
print(ans)

Fixed submission:
n=int(input())
a=list(map(int, input().split()))
cnt=0
t=0
ans=0
tmp=0
for s in range(n):
    while t<n and tmp^a[t]==tmp+a[t]:
        tmp=tmp^a[t]
        t+=1
    ans+=t-s   
    tmp-=a[s]
print(ans)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
a=[]
for i in range(len(s)):
    for j in range(i+1, min(i+k, len(s)+1)):
        a.append(s[i:j])
b=list(set(a))
b.sort()
print(b[k-1])

Fixed submission:
s=input()
k=int(input())
substrings=set()
for i in range(len(s)):
    for j in range(5):
        if i+j<len(s):
            substrings.add(s[i:i+j+1])
substrings=sorted(list(substrings))
print(substrings[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
k=int(input())
a=[]
for i in range(len(s)):
    for j in range(i+1, max(i+k, len(s)+1)):
        a.append(s[i:j])
b=list(set(a))
b.sort()
print(b[k-1])


Fixed submission:
s=input()
k=int(input())
substrings=set()
for i in range(len(s)):
    for j in range(5):
        if i+j<len(s):
            substrings.add(s[i:i+j+1])
substrings=sorted(list(substrings))
print(substrings[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for i in range(29):
    res = 0
    bit = 1<<i
    p = bit
    q = p*2
    r = p*3
    s = p*4
    C = [b&(q-1) for b in B]
    C.sort()
    for a in A:
        a&=q-1
        j = bisect.bisect_left(C, p-a)
        k = bisect.bisect_left(C, q-a)
        res+=(k-j)
        j = bisect.bisect_left(C, r-a)
        k = bisect.bisect_left(C, s-a)
        res+=(k-j)
    if res%2 == 1:
        ans+=bit
print(ans)






Fixed submission:
import numpy as np
N = int(input())
A = np.array(input().split(), dtype = np.int32)
B = np.array(input().split(), dtype = np.int32)
ans = 0
for i in range(29)[::-1]:
    res = 0
    p = 1<<i
    A&=(p*2-1)
    B&=(p*2-1)
    B.sort()
    i, j, k = [np.searchsorted(B, t-A).sum() for t in [p, p*2, p*3]]
    res = (i+k-j)
    if (N-res)%2:
        ans+=p
print(ans)
Buggy python submission (verdict: Runtime Error):
a=input()
b=input()
c=input()
x=input()
t=0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i+100*j+50*k==x:
        t+=1
print(t)

Fixed submission:
a=int(input())
b=int(input())
c=int(input())
x=int(input())
t=0
for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*i+100*j+50*k==x:
        t+=1
print(t)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
#input = sys.stdin.readline
INF = 10**18
mod = 10**9+7
def dijkstra(start, n, graph):
    route_cnt = [start] * n
    route_cnt[start] = 1
    que = [(0, start)]
    dist = [INF] * n
    dist[start] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for c, v in graph[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                route_cnt[v] = route_cnt[u]
                heappush(que, (dist[u] + c  , v))
            elif dist[u] + c == dist[v]:
                route_cnt[v] = (route_cnt[v] + route_cnt[u]) % mod
    return route_cnt, dist
N, M = map(int, input().split())
S, T = map(int, input().split())
G = [[] for _ in range(N)]
edges = []
for _ in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((d, v-1))
    G[v-1].append((d, u-1))
    edges.append((v-1, u-1, d))
num_s, dist_s = dijkstra(S-1, N, G)
num_t, dist_t = dijkstra(T-1, N, G)
ans = num_s[T-1]**2%mod
l = dist_s[T-1]
for u, v, d in edges:
    if dist_s[v]<dist_s[u]:
        u, v = v, u
    if dist_s[u]*2<l<dist_s[v]*2 and dist_s[u]+dist_t[v]+d == l:
        ans-=(num_s[u]*num_t[v])**2
        ans%=mod
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=(num_t[v]*num_s[v])**2
        ans%=mod
print(ans%mod)







Fixed submission:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline
INF = 10**18
mod = 10**9+7
def dijkstra(start, n, graph):
    route_cnt = [start] * n
    route_cnt[start] = 1
    que = [(0, start)]
    dist = [INF] * n
    dist[start] = 0
    while que:
        min_dist, u = heappop(que)
        if min_dist > dist[u]:
            continue
        for c, v in graph[u]:
            if dist[u] + c < dist[v]:
                dist[v] = dist[u] + c
                route_cnt[v] = route_cnt[u]
                heappush(que, (dist[u] + c  , v))
            elif dist[u] + c == dist[v]:
                route_cnt[v] = (route_cnt[v] + route_cnt[u]) % mod
    return route_cnt, dist
N, M = map(int, input().split())
S, T = map(int, input().split())
G = [[] for _ in range(N)]
edges = []
for _ in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((d, v-1))
    G[v-1].append((d, u-1))
    edges.append((v-1, u-1, d))
num_s, dist_s = dijkstra(S-1, N, G)
num_t, dist_t = dijkstra(T-1, N, G)
ans = num_s[T-1]**2%mod
l = dist_s[T-1]
for u, v, d in edges:
    if dist_s[v]<dist_s[u]:
        u, v = v, u
    if dist_s[u]*2<l<dist_s[v]*2 and dist_s[u]+dist_t[v]+d == l:
        ans-=(num_s[u]**2%mod)*(num_t[v]**2%mod)
        ans%=mod
for v in range(N):
    if dist_s[v] == dist_t[v] == l/2:
        ans-=(num_t[v]**2%mod)*(num_s[v]**2%mod)
        ans%=mod
print(ans%mod)
Buggy python submission (verdict: Runtime Error):
def travel(x,y,t):
    for i in range(t):
        if x+y==t-2*i:
            return True
    return False
n=int(input())
for i in range(n):
    t, x, y = [int(j) for j in input().split() ]
    if not travel(x,y,t):
        print("No")
        exit()
print("Yes")    


Fixed submission:
a,b=[int(i) for i in input().split()]
if a*b%2==1:
  print('Odd')
else:
  print('Even')

Buggy python submission (verdict: Runtime Error):
i=input()
j=input()
int(i)
int(j)
if i*j%2==1:
  print('Odd')
else:
  print('Even')

Fixed submission:
a,b=[int(i) for i in input().split()]
if a*b%2==1:
  print('Odd')
else:
  print('Even')
Buggy python submission (verdict: Time Limit Exceeded):
def travel(x,y,t):
    for i in range(t):
        if x+y==t-2*i:
            return True
    return False
n=int(input())
for i in range(n):
    t, x, y = [int(j) for j in input().split() ]
    if not travel(x,y,t):
        print("No")
        exit()
print("Yes")    


Fixed submission:
n=int(input())
txy=[[0, 0, 0]]+[list(map(int, input().split())) for i in range(n)]
def C(txy0, txy1):
    xx=txy1[1]-txy0[1]
    yy=txy1[2]-txy0[2]
    tt=txy1[0]-txy0[0]
    if xx+yy<=tt and (xx+yy-tt)%2==0:
        return True
    return False
if all(C(txy[i], txy[i+1]) for i in range(n)):
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
prime=[]
n=10**5
is_prime=True
for i in range(2,n+1):
    is_prime=True
    for p in prime:
        if i%p==0:
            is_prime=False
            break
    if is_prime:
        prime.append(i)
q=int(input())
query=[[int(i) for i in input().split()] for j in range(q)]
for qu in query:
    cnt=0
    for j in range(qu[0], qu[1]+1, 2):
        if (j in prime) and (((j+1)//2) in prime):
            cnt+=1
    print(cnt)        


Fixed submission:
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

num = 10**5+10
Q = int(input())
prime_numbers = primes(num)
prime_set = set(prime_numbers)
prime_count = [0]*(num+1)
for pi in prime_numbers:
    if (pi+1)//2 in prime_set:
        prime_count[pi]+=1
for i in range(num):
    prime_count[i+1]+=prime_count[i]
for i in range(Q):
    l, r = map(int, input().split())
    print(prime_count[r]-prime_count[l-1])
Buggy python submission (verdict: Runtime Error):
import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
    else:
      print(t)
      sys.exit()
  t+=1
      


Fixed submission:
a=input()
print(a.count('1'))

Buggy python submission (verdict: Runtime Error):
import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
    else:
      print(t)
      sys.exit()
  t+=1
      

Fixed submission:
a=input()
print(a.count('1'))

Buggy python submission (verdict: Runtime Error):
import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
    else:
      print(t)
      sys.exit()
	t+=1
      

Fixed submission:
a=input()
print(a.count('1'))

Buggy python submission (verdict: Runtime Error):
import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
      t+=1
    else:
      print(t)
      sys.exit()
      


Fixed submission:
a=input()
print(a.count('1'))

Buggy python submission (verdict: Runtime Error):
a=input()
c=0
for i in range(2):
  if a>=10**(2-i):
    a-10**(2-i)
    c+=1
print(c)

Fixed submission:
a=input()
print(a.count('1'))
Buggy python submission (verdict: Runtime Error):
import sys
N=input()
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
      t+=1
    else:
      print(t)
      sys.exit()
      

Fixed submission:
import sys
N=int(input())
a=[int(i) for i in input().split()]
t=0
while True:
  for i in range(N):
    if a[i]%2==0:
      a[i]//=2
    else:
      print(t)
      sys.exit()
  t+=1
Buggy python submission (verdict: Runtime Error):
N, C = map(int, input().split())
num = 10#**5+1
count = [0]*(num)
channel = [0]*num
for i in range(N):
    s, t, c = map(int, input().split())
    print(count)
    if channel[s]==c and channel[t-1]==c:
        count[s]+=1
        count[t-1]-=1
    elif channel[s]==c:#はじめ＝終わり
        count[s]+=1
        count[t]-=1
    elif channel[t-1]==c:
        count[t-1]-=1
        count[s-1]+=1
    else:
        count[s-1]+=1
        count[t]-=1
    channel[s-1]=c
    channel[t]=c
print(count)
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Fixed submission:
T_max = 10**5
N, C = map(int, input().split())
channel = [[] for _ in range(C)]
time = [0]*(T_max+2)
for i in range(N):
    s, t, c = map(int, input().split())
    channel[c-1].append((s, t))
for c in channel:
    c.sort()
    if len(c)==0:
        continue
    time[c[0][0]]+=1
    for i in range(1, len(c)):
        if c[i-1] [1] != c[i][0]:
            time[c[i-1][1]+1] -= 1
            time[c[i][0]]+=1
    time[c[-1][1]+1]-=1
for i in range(1, T_max+1):
    time[i] = time[i-1]+time[i]
print(max(time))

Buggy python submission (verdict: Runtime Error):
N, C = map(int, input().split())
num = 10*5+1
count = [0]*(num)
for i in range(N):
    s, t, c = map(int, input().split())
    count[s-1]+=1
    count[t]-=1
for i in range(1, num):
    count[i]+=count[i-1]
print(max(count))

Fixed submission:
T_max = 10**5
N, C = map(int, input().split())
channel = [[] for _ in range(C)]
time = [0]*(T_max+2)
for i in range(N):
    s, t, c = map(int, input().split())
    channel[c-1].append((s, t))
for c in channel:
    c.sort()
    if len(c)==0:
        continue
    time[c[0][0]]+=1
    for i in range(1, len(c)):
        if c[i-1] [1] != c[i][0]:
            time[c[i-1][1]+1] -= 1
            time[c[i][0]]+=1
    time[c[-1][1]+1]-=1
for i in range(1, T_max+1):
    time[i] = time[i-1]+time[i]
print(max(time))