Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

dp=np.zeros((n+1,w+1),np.int64)
# dp[i][j]:重さjを超えないようにしながらi個目までの商品を取るか取らないか選んだ時の価値の最大
# dp[i][0]=0,dp[0][j]=0,dp[n][inf]=sum(v) 求めるのはdp[n][w]
# 重さの小さい方から探索
for j in range(1,w+1):
      for i in range(1,n+1):
            m1=dp[i-1][j]
            m2=dp[i-1][j-wv[i-1][0]]+wv[i-1][1] if j-wv[i-1][0]>=0 else 0
            dp[i][j]=max(m1,m2)
            
print(dp[n][w])

Fixed submission:
import numpy as np
n,w=map(int,input().split())
wv=[]
for _ in range(n):
      wv.append(list(map(int,input().split())))

# dp[j]:重さの総和がj以下となるように選択した時の最大
dp=np.zeros(w+1,np.int64)
for i in range(n):
      # i+1個目までの商品の中から選ぶときのdpを計算する
      # i+1個目の計算をするときはdpはi個目までの商品の中から選んだ時のdpとなっている
      # i=0 ->dp=zeros
      w_=wv[i][0]
      v_=wv[i][1]
      # dp[w_:]:i+1個目の商品を加えられるのはこの部分のみ。
      # dp[w_:]:i+1個目の商品を加えないパターン
      # dp[:-w_]+v_:i+1個目の商品を加えたパターン。商品の重さだけwを減らした時の最大価値に商品の価値をプラスしている。
      dp[w_:] = np.maximum(dp[w_:], dp[:-w_] + v_)
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[v]:
                  res=max(res,dp(u)+1)
            memo[v]=res
            visited[v]=True
            return res
for i in range(n):
      dp(i)
print(max(memo))


Fixed submission:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[v]:
                  res=max(res,dp(u)+1)
            memo[v]=res
            visited[v]=True
            return res
for i in range(n):
      dp(i)
print(max(memo))

Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(m)]
# dp[j][k]:頂点iからはじまり頂点jで終わる最長のもの
dp=np.full((n,n),-1,np.int64)
for i in range(n):
      dp[i][i]=0
for _ in xy:
      x_=_[0]-1
      y_=_[1]-1
      dp[x_,y_]=1
      x0=np.where(dp[:,x_] >= 0)[0]
      y0=np.where(dp[y_,:] >= 0)[0]
      for j in x0:
            for k in y0:
                  dp[j,k]=max(dp[j,k],dp[j,x_]+dp[y_,k]+1)
print(np.max(dp))

Fixed submission:
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n,m = map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
      x,y=map(int,input().split())
      g[x-1].append(y-1)
memo = [0]*n
visited = [False]*n
# dp(i):i=0,1,..,n-1:頂点iを始点とした最長のパスを返す
def dp(v):
      if visited[v]:
            return memo[v]
      else:
            res=0
            for u in g[v]:
                  res=max(res,dp(u)+1)
            memo[v]=res
            visited[v]=True
            return res
for i in range(n):
      dp(i)
print(max(memo))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(w)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)


Fixed submission:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[[s=='.' for s in list(input())] for _ in range(h)]
#h,w=1000,1000
#a=[[True]*w]*h
mod=10**9+7
dp=np.zeros((h,w),np.int64)

novisited=np.array(a)
novisited[0,:]=False
novisited[:,0]=False
memo=np.zeros((h,w),np.int64)
for i in range(h):
      if a[i][0]:
            memo[i,0]=1
      else:
            break
for i in range(w):
      if a[0][i]:
            memo[0,i]=1
      else:
            break
def dp(i,j):
      if not novisited[i][j]:
            return memo[i,j]
      else:
            memo[i,j]=(dp(i-1,j)+dp(i,j-1))%mod
            novisited[i][j]=False
            return memo[i,j]

print(dp(h-1,w-1))

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[[s=='.' for s in list(input())] for _ in range(h)]
mod=10**9+7
dp=np.zeros((h,w),np.int64)
for i in range(h):
      if a[i][0]:
            dp[i,0]=1
      else:
            break
for j in range(w):
      if a[0][j]:
            dp[0,j]=1
      else:
            break
for i in range(1,h):
      for j in range(1,w):
            dp[i,j]=(dp[i-1,j]+dp[i,j-1])%mod if a[i][j] else 0
print(dp[-1][-1])

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
h,w = map(int,input().split())
a=[input() for _ in range(h)]
mod=10**9+7
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
      for j in range(w):
            if i+1<h and a[i+1][j]=='.':
                  dp[i+1][j]+=dp[i][j]%mod
            if j+1<w and a[i][j+1]=='.':
                  dp[i][j+1]+=dp[i][j]%mod
print(dp[-1][-1]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=pow(10,9)+7
dp=np.zeros((n+1,k+1),np.int64)# dp[i+1][j]:i人でj個の飴を分ける分け方。人が一人以上のとき、0個の時は明らかに1通り。0人に飴を分ける方法はないので0通り
sdp=np.zeros(k+2,np.int64)
dp[:,0]=1
dp[0,:]=0 # dp[0,0]=0
dp[1,:a[0]+1]=1 #一人目だけいる時、その人が持てる飴の個数以下なら1
for i in range(1,n):
      # 累計和にする
      s=0
      for l in range(k+1):
        s+=dp[i,l]
        sdp[l+1]=s%mod
      dp[i+1,1:]=np.array([(sdp[j+1]-sdp[max(0,j-a[i])])%mod for j in range(1,k+1)])
print(dp[-1][-1]%mod)



Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100,100000
#a=[k//2]*n
mod=pow(10,9)+7
dp=[0]*(k+1) # dp[j]:j個の飴を分ける分け方。人が一人以上のとき、0個の時は明らかに1通り。0人に飴を分ける方法はないので0通り
sdp=[0]*(k+2)
for i in range(a[0]+1):#一人目だけいる時、その人が持てる飴の個数以下なら1
  dp[i]=1 
for i in range(1,n):
      # 累計和にする
      s=0
      for l in range(k+1):
            s+=dp[l]
            sdp[l+1]=s%mod
      for j in range(1,k+1):
        dp[j]=(sdp[1+j]-sdp[max(0,j-a[i])])%mod
print(dp[-1]%mod)
Buggy python submission (verdict: Runtime Error):
s=list(map(int,list(input())))
# s[0]=1,s[-1]=0,s[k]=s[n-k-1]は必要
def main(s):
  n=len(s)
  if s[0]!=1 or s[-1]!=0:return [-1]
  for k in range(n//2-1):
    if s[k]!=s[n-k-2]:return [-1]
  uv=[(1,2)]
  t=2
  i=3
  for x in s[1:-1]:
    uv.append((t,i))
    if x==1:
      t=i
    i+=1
  return uv
for x in main(s):
  print(*x,sep=' ')


Fixed submission:
s=list(input())
n=len(s)
if s[0]=='0' or s[-1]=='1':
  print(-1)
else:
  s.pop()
  sr=s.copy()
  sr.reverse()
  if s!=sr:
    print(-1)
  else:
    ans=[]
    now=1
    cnt=1
    for x in s:
      if x=='1':
        ans.append([now,now+cnt])
        now+=cnt
        cnt=1
      else:
        ans.append([now,now+cnt])
        cnt+=1
    for x in ans:
      print(x[0],x[1])
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
st={}
for i in range(len(s)):
    if s[i]!=t[i]:
        si=s[i]
        ti=t[i]
        s=s.replace(si,'0')
        s=s.replace(ti,si)
        s=s.replace('0',ti)
print('Yes' if s==t else 'No')
#print(s,t)


Fixed submission:
s=input()
t=input()
ns,nt=0,0
anss,anst=s,t
sl,tl=[],[]
for i in range(len(s)):
    if s[i] in sl:
        pass
    else:
        ns+=1
        sl.append(s[i])
        anss=anss.replace(s[i],str(ns))
    if t[i] in tl:
        pass
    else:
        nt+=1
        tl.append(t[i])
        anst=anst.replace(t[i],str(nt))
print('Yes' if anss==anst else 'No')

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
t=input()
st={}
for i in range(len(s)):
    if s[i]!=t[i]:
        si=s[i]
        ti=t[i]
        s=s.replace(si,'0')
        s=s.replace(ti,si)
        s=s.replace('0',ti)
print('Yes' if s==t else 'No')
#print(s,t)


Fixed submission:
s=input()
t=input()
ns,nt=0,0
anss,anst=s,t
sl,tl=[],[]
for i in range(len(s)):
    if s[i] in sl:
        pass
    else:
        ns+=1
        sl.append(s[i])
        anss=anss.replace(s[i],str(ns))
    if t[i] in tl:
        pass
    else:
        nt+=1
        tl.append(t[i])
        anst=anst.replace(t[i],str(nt))
print('Yes' if anss==anst else 'No')
Buggy python submission (verdict: Time Limit Exceeded):
n,m,q_=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
pq=[list(map(int,input().split())) for _ in range(q_)]
from collections import defaultdict
dmap=defaultdict(int)
smap=defaultdict(int)
for l,r in lr:
  dmap[(l,r)]+=1
for i in range(1,n+1):
  tmp=0
  for j in range(i,n+1):
    tmp+=dmap[(i,j)]
    smap[(i,j)]=tmp
for p,q in pq:
  ans=0
  for i in range(p,q+1):
    ans+=smap[(i,q)]
  print(ans)

Fixed submission:
n,m,q_=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
pq=[list(map(int,input().split())) for _ in range(q_)]
from collections import defaultdict
dmap=defaultdict(int)
smap=defaultdict(int)
ssmap=defaultdict(int)
for l,r in lr:
  if (l,r) in dmap:
    dmap[(l,r)]+=1
  else:
    dmap[(l,r)]=1
for i in range(1,n+1):
  tmp=0
  for j in range(i,n+1):
    if (i,j) in dmap:
      tmp+=dmap[(i,j)]
    smap[(i,j)]=tmp
for i in range(1,n+1):
  tmp=0
  for j in range(1,i+1):
    tmp+=smap[(j,i)]
    ssmap[(j,i)]=tmp

for p,q in pq:
  ans=ssmap[(q,q)]-ssmap[(p-1,q)]
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main(n,a):
  import numpy as np
  a=np.array([a[i]-i for i in range(n)])
  #print(a)
  #print(len(a[a<0]))
  #print(len(a[a>0]))
  if len(a[a<0])==len(a[a>0]):
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])>len(a[a>0]):
    while len(a[a<0])>len(a[a>=0]):
      a+=np.min(a[a<0])
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])<len(a[a>0]):
    while len(a[a<=0])<len(a[a>0]):
      a-=np.min(a[a>0])
    print(sum(list(map(abs,a))))
    exit()
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i] -= i + 1
a.sort()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))

Buggy python submission (verdict: Time Limit Exceeded):
def main(n,a):
  import numpy as np
  a=np.array([a[i]-i for i in range(n)])
  #print(a)
  #print(len(a[a<0]))
  #print(len(a[a>0]))
  if len(a[a<0])==len(a[a>0]):
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])>len(a[a>0]):
    while len(a[a<0])>len(a[a>=0]):
      a+=1
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])<len(a[a>0]):
    while len(a[a<=0])<len(a[a>0]):
      a-=1
    print(sum(list(map(abs,a))))
    exit()
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i] -= i + 1
a.sort()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
a.sort()
s=0
for i in range(n):
    a[i] -= i + 1
    s += a[i]
b1 = a[n // 2]
b2 = a[(n // 2 )+ 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i] -= i + 1
a.sort()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))
Buggy python submission (verdict: Time Limit Exceeded):
def main(n):
  if n<6:
    print(n)
    exit()
  l=[6**i for i in range(7)]
  l[6:6]=[9**i for i in range(1,6)]
  l.sort()
  if n in l:
    print(1)
    exit()
  from collections import deque
  todo=deque([[1,li] for li in l[1:] if n>li])
  while len(todo)>0:
    d=todo.popleft()
    t0=d[0]
    t1=d[1]
    for li in [li for li in l if li<=n-d[1]]:
      if t1+li==n:
        print(t0+1)
        exit()
      else:
        todo.append([t0+1,t1+li])

if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  main(n)

Fixed submission:
def dfs(a,b,c):
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    l=len(t)
    if l==a:
      ret.append(t)
    else:
      s=0
      for i in range(1,l+1):
        s+=6**i*t[i-1]
      for i in range(b+1):
        if s+6**(l+1)*i<=c:
          tc=t.copy()
          tc.append(i)
          todo.append(tc)
  return ret
a=6
b=5
c=int(input())
l=dfs(a,b,c)
ans=c
for li in l:
  ansi=sum(li)
  now=c-sum([6**(i+1)*li[i]for i in range(len(li))])
  for i in range(1,7):
    ansi+=now%9
    now//=9
  ans=min(ans,ansi)
print(ans)
Buggy python submission (verdict: Runtime Error):
n,nc=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(nc)]
c=[list(map(int,input().split())) for _ in range(n)]

dct={}
for x in range(n):
  for y in range(n):
    for ci in range(nc):
      if (ci,(x+y)%3) in dct:
        dct[(ci,(x+y)%3)]+=d[c[x][y]-1][ci]
      else:
        dct[(ci,(x+y)%3)]=d[c[x][y]-1][ci]

def func(x,y,z): #(i+j)%=0をxに、=1をyに、=2をzに塗るときの違和感
  ret=dct[(x,0)]+dct[(y,1)]+dct[(z,2)]
  return ret
ans=float('inf')
for x in range(nc):
  for y in range(nc):
    if x==y:continue
    for z in range(nc):
      if x==z or z==y:continue
      ans=min(ans,func(x,y,z))
print(ans)
#print(dct)

Fixed submission:
n,nc=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(nc)]
c=[list(map(int,input().split())) for _ in range(n)]
from collections import defaultdict
dct=defaultdict(int)
for x in range(n):
  for y in range(n):
    for ci in range(nc):
      if (ci,(x+y)%3) in dct:
        dct[(ci,(x+y)%3)]+=d[c[x][y]-1][ci]
      else:
        dct[(ci,(x+y)%3)]=d[c[x][y]-1][ci]

def func(c1,c2,c3): #(i+j)%=0をc1に、=1をc2に、=2をc3に塗るときの違和感
  ret=dct[(c1,0)]+dct[(c2,1)]+dct[(c3,2)]
  return ret
ans=float('inf')
for c1 in range(nc):
  for c2 in range(nc):
    if c1==c2:continue
    for c3 in range(nc):
      if c1==c3 or c2==c3:continue
      ans=min(ans,func(c1,c2,c3))
print(ans)
#print(dct)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
k=[[0]*20 for i in range(n)]
for i in range(n):
    for j in range(20):
        k[i][j] = 1 if (a[i] % 2**(j+1)) >= 2**j else 0
l=0
r=0
c20=[0]*20
r0=-1
ans=[0]*n
while l < n:
    if r > r0:
        for _ in range(20):
            c20[_]+=k[r][_]
    else:
        for _ in range(20):
            c20[_]-=k[l-1][_]
    l0=l
    r0=r
    if sum(list(map(lambda x:x>1 ,c20))) == 0:
        ans[l]=max(ans[l],r)
        if r < n-1:
            r+=1
        else:
            l+=1
    else:
        ans[l]=max(ans[l],r-1)
        l+=1
s=0
for i in range(n):
    s+=ans[i]-i+1
print(s)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
l=0
r=0
now=0
ans=[0]*n
while l < n:
    if r < n and now^a[r] == now + a[r]:
        now += a[r]
        ans[l]=r
        r+=1
    else:
        now -= a[l]
        l+=1
        ans[l-1]=r-1
print(sum([ans[i]-i+1 for i in range(n)]))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
k=[[0]*20 for i in range(n)]
for i in range(n):
    for j in range(20):
        k[i][j] = 1 if (a[i] % 2**(j+1)) >= 2**j else 0

l=0
r=0
c20=[0]*20
r0=-1
ans=[0]*n
while l < n:
    if r > r0:
        for _ in range(20):
            c20[_]+=k[r][_]
    else:
        for _ in range(20):
            c20[_]-=k[l-1][_]
    l0=l
    r0=r
    if sum(list(map(lambda x:x>1 ,c20))) == 0:
        ans[l]=max(ans[l],r)
        if r < n-1:
            r+=1
        else:
            l+=1
    else:
        ans[l]=max(ans[l],r-1)
        l+=1
print(sum([ans[i]-i+1 for i in range(n)]))


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
l=0
r=0
now=0
ans=[0]*n
while l < n:
    if r < n and now^a[r] == now + a[r]:
        now += a[r]
        ans[l]=r
        r+=1
    else:
        now -= a[l]
        l+=1
        ans[l-1]=r-1
print(sum([ans[i]-i+1 for i in range(n)]))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
a_sum=[0]
s=0
for ai in a:
    s+=ai
    a_sum.append(s)
# print(a_sum)
k=[[0]*20 for i in range(n)]
for i in range(n):
    for j in range(20):
        k[i][j] = 1 if (a[i] % 2**(j+1)) >= 2**j else 0
a_xor=[[0]*20]
s=[0]*20
for ki in k:
    xori=[]
    for j in range(20):
        xori.append((s[j]+ki[j]) % 2)
    a_xor.append(xori)
    s=xori
# print(a_xor)
# 2 5 4 6 -> 2 7 3 5
ans=0
for l in range(1,n+1):
    for r in range(l,n+1):
        xor = sum([((a_xor[l-1][i]+a_xor[r][i]) % 2) * 2**i for i in range(20)])
        if a_sum[r]-a_sum[l-1]==xor:
            ans+=1
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
l=0
r=0
now=0
ans=[0]*n
while l < n:
    if r < n and now^a[r] == now + a[r]:
        now += a[r]
        ans[l]=r
        r+=1
    else:
        now -= a[l]
        l+=1
        ans[l-1]=r-1
print(sum([ans[i]-i+1 for i in range(n)]))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
  for j in range(n):
    a=ss[i:i+n,j:j+n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans)

Fixed submission:
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)

Buggy python submission (verdict: Runtime Error):
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
  for j in range(n):
    a=ss[i:i+n,j:j+n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans)

Fixed submission:
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=[list(input()) for _ in range(n)]
ss=[si+si for si in s]
ss=ss+ss
ans=0
for i in range(n):
  for j in range(n):
    a=[si[j:j+n] for si in ss[i:i+n]]
    flg=True
    for k in range(n-1):
      a1=a[k][k+1:]
      a2=[a[i+1][k] for i in range(k,n-1)]
      if a1!=a2:
        flg=False
        break
    if flg:ans+=1
print(ans)

Fixed submission:
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=[list(input()) for _ in range(n)]
ss=[si+si for si in s]
ss=ss+ss
ans=0
for i in range(n):
  for j in range(n):
    a=[si[j:j+n] for si in ss[i:i+n]]
    flg=True
    for k in range(n):
      for l in range(n):
        if a[k][l]!=a[l][k]:
          flg=False
          break
      if not flg:
        break
    if flg:ans+=1
print(ans)

Fixed submission:
n=int(input())
s=[list(input()) for _ in range(n)]
import numpy as np
ss=[si+si for si in s]
ss=np.array(ss+ss)
ans=0
for i in range(n):
    a=ss[i:i+n,:n]
    if np.array_equal(a,a.T):
      ans+=1
print(ans*n)
Buggy python submission (verdict: Runtime Error):
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
for a,b in ab:
    if a>b:a,b=b,a
    if a==b:
        print(2*a-2)
    elif a+1==b:
        print(2*a-2)
    else:
        c=int((a*b)**0.5)
        if c*(c+1)>=a*b:
            print(2*c-2)
        elif c**2<a*b:
            print(2*c-1)


q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
    # a*bをぎりぎりまで攻めたい
    # (1,1)とかはもったいない。(1,a*b-1)は良い。片方は√a*b未満で、片方は√a*bより大きい組み合わせ。
    # a==bならa未満の整数yについて適切な数字xを選べばy*x<a*bとできる。xは他のxと被らないように選択できる。
    if a==b:
        print(2*a-2)
    else:
        # t,t+1 組み合わせの積がa*bで抑えられているかどうか。(t+1)*(t+1)は必ずa*bを超える。
        # t未満の自然数については適切な整数を選べばa*b以下にできる。
        t=floor((a*b)**0.5)
        # (1,2*t-1),(2,2*t-2),(3,(a*b-1)//3),...,(t-1,(a*b-1)//(t-1))
        if t*t>=a*b: 
            # t*tはだめ。t*t=a*b、a!=bのとき。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-3)
        elif t*(t+1)>=a*b: 
            # t*tはOK。t*(t+1)はだめ。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            # さらに一回目tの人は2回目もtで条件を満たす。この分を足す。t!=a,t!=bなので(t,t)は選択できる。
            print(2*t-2)
        else:
            # t*tもt*(t+1)もOK。(t,t+1),(t+1,t)をまず選ぶ。あとはt未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-1)


Fixed submission:
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
  if a==b:
    print(2*a-2)
    continue
  t=floor((a*b)**0.5)
  # t,t+1 組み合わせの積がa*bで抑えられているかどうか
  if t*t>=a*b: # t*tもだめ
    print(2*t-3)
  elif t*(t+1)>=a*b: # t*(t+1)はだめ
    print(2*t-2)
  else: # t*tもt*(t+1)もOK
    print(2*t-1)