Harryxun/stf_run huggingface dataset:
import numpy as np

#sys.setrecursionlimit(10 ** 9)

K = int(input())

def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += gcd(gcd(i+1,j+1), k+1)

print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())
mod = 10**9 + 7

N = 3

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

M = np.zeros(K+1, dtype=int)

for i in range(K, 0, -1):
#    print(i)
    M[i] += pow(K//i, N)
    
    for j in range(2,K//i+1):
        j *= i
        M[i] -= M[j]
    
    ans += M[i] * i
    
        
print(ans)
S = input()
rev = S[::-1]

l = int(len(S)/2)
front = S[0:l]
back = rev[0:l]

cnt = 0
moji = 0

for s in front:
    if front[cnt] == back[cnt]:
        moji += 1
    cnt += 1

ans = len - moji
print(ans)

### FIXED CODE ###

S = input() #ここで標準入力
rev = S[::-1]

l = int(len(S)/2)
front = S[0:l]
back = rev[0:l]

cnt = 0
moji = 0

for s in front:
    if front[cnt] == back[cnt]:
        moji += 1
    cnt += 1

ans = l - moji
print(ans)
S = input()

R = []
r = 0
for s in S:
    if s == "R":
        r += 1
    if s == "S":
        R.append(r)
        r = 0

print(max(R))


### FIXED CODE ###

S = input()

R = []
r = 0
for s in S:
    if s == "R":
        r += 1
    if s == "S":
        R.append(r)
        r = 0
    R.append(r)

print(max(R))
import collections

n = int(input())
v = list(map(int,input().split()))
a = [v[i] for i in range(n) if i%2==0]
b = [v[i] for i in range(n) if i%2==1]

a = collections.Counter(a)
b = collections.Counter(b)

A = a.most_common()[:2]
B = b.most_common()[:2]
if A[0][0]==B[0][0]:
    print(n-max(A[0][1]+B[1][1],A[1][1]+B[0][1]))
else:
    print(n-A[0][1]-B[0][1])

### FIXED CODE ###

import collections

n = int(input())
v = list(map(int,input().split()))
a = [v[i] for i in range(n) if i%2==0]
b = [v[i] for i in range(n) if i%2==1]

a = collections.Counter(a)
b = collections.Counter(b)

A = a.most_common()[:2]
A.append(("x",0))
B = b.most_common()[:2]
B.append(("x",0))
if A[0][0]==B[0][0]:
    print(n-max(A[0][1]+B[1][1],A[1][1]+B[0][1]))
else:
    print(n-A[0][1]-B[0][1])
import sys
c = 1
for i in sys.stdin.readlines() :
    l = list(int, i.split())
    a = l[0]
    b = l[1]
    if a == 0 and b == 0 :
        break
    else :
        sorted(l)
        print(l[0],l[1])
        c = c + 1

### FIXED CODE ###

import sys
while True :
    ab = list(map(int,sys.stdin.readline().split()))
    a = ab[0]
    b = ab[1]
    if a == 0 and b == 0 :
        break
    else :
        ab = sorted(ab)
        print(ab[0],ab[1])
##### 解けた #####

n=list(map(int,list(input())))
no=[] # 出力

for ni in n:
    no.append(10-ni)

print("".join(no))

### FIXED CODE ###

##### 解けた #####

n=list(map(int,list(input())))
no=[] # 出力

for ni in n:
    no.append(str(10-ni))

print("".join(no))
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
temp=0
an,bn=0,0
ans=0
while temp<=k:
    if an==n and bn==m: break
    if an>=n:
        temp+=b[bn]
        if temp>k: break
        bn+=1
    elif bn>=m:
        temp+=a[an]
        if temp>k: break
        an+=1
    else:
        if a[an]<b[bn]:
            temp+=a[an]
            if temp>k: break
            an+=1
        elif a[an]>b[bn]:
            temp+=b[bn]
            if temp>k: break
            bn+=1
        else:
            cnt=0
            while True:
                if a[an]<b[bn]:
                    temp+=a[an]
                    an+=1
                    bn-=cnt
                    break
                elif a[an]>b[bn]:
                    temp+=b[bn]
                    bn+=1
                    an-=cnt
                    break
                if an==n:
                    break
                if bn==m:
                    break
                temp+=a[an]
                if temp>k:
                    break
                an+=1
                bn+=1
                ans+=1
                cnt+=1
            if temp>k:
                break
    ans+=1
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=[0]+list(map(int,input().split()))
b=[0]+list(map(int,input().split()))

for i in range(1,n+1): a[i]=a[i]+a[i-1]
for i in range(1,m+1): b[i]=b[i]+b[i-1]
j=m
ans=0
for i in range(n+1):
    if j<0: break
    while a[i]+b[j]>k and j>=0: j-=1
    ans=max(i+j,ans)
print(ans)
n,m,d=map(float,input().split())
print((m-1.0)*(n-d)*((d>0.0)?2.0:1.0)/(n*n));

### FIXED CODE ###

n,m,d=map(float,input().split())
print((m-1)*(n-d)*([1,2][d>0])/n**2);
n,m=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)[::-1]
s=sum(a)
print("Yes" if a[m]>=s/4/m else "No")


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)[::-1]
s=sum(a)
print("Yes" if a[m-1]>=s/4/m else "No")
s=100
x=int(input())
i=0
While True:
  if s>=x:
    break
  s=s*1.01
  i=i+1
  
print(i+1)

### FIXED CODE ###

s=100
i=0
x=int(input())
 
while True:
  if s>=x:
    break
  else:
    i=i+1
    s=int(s*1.01)
    
print(i)
A = int(input())
B = int(input())
if 1 <= A and A <=9 and 1 <= B and B <=9 :
    print(A*B)
else:
    print(-1)

### FIXED CODE ###

A,B = map(int,input().split())
if 1 <= A and A <=9 and 1 <= B and B <=9 :
    print(A*B)
else:
    print(-1)
n, m, x = map(int, input().split())

A = [[] for _ in range(n)]
c = [0] * n

INF = 10**9
ans = INF

for i in range(n):
  c_as = list(map(int, input().split()))
  c[i], A[i] = c_as[0], c_as[1:]
  
for s in range(0, 1 << n):
  skill = [0] * n
  money = 0
  for i in range(n):
    if(s >> i) % 2 == 0:continue
    money += c[i]
    for j in range(m):
      skill[j] += A[i][j]
  ok = True
  for j in range(m):
    if skill[j] < x:
      ok = False
  if ok:
    ans = min(ans, money)
    
if ans == INF:
  ans = -1
  
print(ans)

### FIXED CODE ###

n, m, x = map(int, input().split())

A = [[] for _ in range(n)]
c = [0] * n

for i in range(n):
  c_as = list(map(int, input().split()))
  c[i], A[i] = c_as[0], c_as[1:]

INF = 10**9
ans = INF
  
for s in range(0, 1 << n):
  skill = [0] * m
  money = 0
  for i in range(n):
    if(s >> i) % 2 == 0:continue
    money += c[i]
    for j in range(m):
      skill[j] += A[i][j]
  ok = True
  for j in range(m):
    if skill[j] < x:
      ok = False
  if ok:
    ans = min(ans, money)
    
if ans == INF:
  ans = -1
  
print(ans)
n=int(input())
l=list(map(int,input().split()))
from collections import defaultdict
d=defaultdict(int)
l1=set(l)
l2=[]
for i in l:
  d[i]+=1
if len(d)==1:
  if l[0]==0:
    print("Yes")
  else:
    print("No")
elif len(d)==2:
  for i in l1:
    l2.append(i)
  bool1=True
  if d[l2[0]]==d[l2[1]]*2:
    a=l2[0]
    b=l2[0]
    c=l2[1]
  elif d[l2[0]]*2==d[l2[1]]:
    a=l2[0]
    b=l2[1]
    c=l2[1]
  else:
    boo11=False
  if bool1:
    l2=[a,b,c]
    l2=sorted(l2)
    a=l2[2]
    b=l2[1]
    c=l2[0]
    la=[]
    lb=[]
    lc=[]
    while a!=0:
      la.append(a%2)
      a=a//2
    while b!=0:
      lb.append(b%2)
      b=b//2
    while c!=0:
      lc.append(c%2)
      c=c//2
    if lc==[]:
      lc=[0]
    if lb==[]:
      lb=[0]
    while len(lb)<len(la):
      lb.append(0)
    while len(lc)<len(la):
      lc.append(0)
    bool1=True
    for i in range(len(la)):
      if la[i]+lb[i]+lc[i]==1 or la[i]+lb[i]+lc[i]==3:
        bool1=False
    if bool1:
      print("Yes")
    else:
      print("No")
  else:
    print("No")  
elif len(d)==3:
  for i in l1:
    l2.append(i)
  l2=sorted(l2)
  if d[l2[0]]==d[l2[1]] and d[l2[1]]==d[l2[2]]:
    a=l2[2]
    b=l2[1]
    c=l2[0]
    la=[]
    lb=[]
    lc=[]
    while a!=0:
      la.append(a%2)
      a=a//2
    while b!=0:
      lb.append(b%2)
      b=b//2
    while c!=0:
      lc.append(c%2)
      c=c//2
    if lc==[]:
      lc=[0]
    while len(lb)<len(la):
      lb.append(0)
    while len(lc)<len(la):
      lc.append(0)
    bool1=True
    for i in range(len(la)):
      if la[i]+lb[i]+lc[i]==1 or la[i]+lb[i]+lc[i]==3:
        bool1=False
    if bool1:
      print("Yes")
    else:
      print("No")           
  else:
    print("No")
else:
  print("No")

### FIXED CODE ###

n=int(input())
def xor(x,y):
  bitx=[]
  bity=[]
  num1,num2=x,y
  while num1!=0:
    bitx.append(num1%2)
    num1//=2
  while num2!=0:
    bity.append(num2%2)
    num2//=2
  m=max(len(bitx),len(bity))
  while len(bitx)<m+1:
    bitx.append(0)
  while len(bity)<m+1:
    bity.append(0)
  ans=0
  for i in range(m):
    if bitx[i]!=bity[i]:
      ans+=2**i
  return ans
from collections import defaultdict
import sys
d=defaultdict(int)
l=list(map(int,input().split()))
if n%3!=0:
  for i in range(n):
    if l[i]!=0:
      print("No")
      sys.exit()
  print("Yes")
  sys.exit()
for i in l:
  d[i]+=1
if len(d)>3:
  print("No")
elif len(d)==3:
  b=True
  l1=[]
  for i in d:
    l1.append(i)
    if d[i]!=n/3:
      b=False
  if l1[0]!=xor(l1[1],l1[2]) or l1[1]!=xor(l1[0],l1[2]) or l1[2]!=xor(l1[0],l1[1]):
    b=False
  if b:
    print("Yes")
  else:
    print("No")
elif len(d)==2:
  if d[0]!=n/3:
    print("No")
  else:
    print("Yes")
else:
  if d[0]==n:
    print("Yes")
  else:
    print("No")
N = int(input())

C = input().split()

B = C[:]
S = C[:]

# bubble sort
flag = 1
while(flag):
    flag = 0
    for x in (1, N):
        if C[x][1:] < C[x-1][1:]:
            C[x], C[x-1] = C[x-1], C[x]
            flag = 1

# sectionSot
for x in range(0,N):
    minj = x
    for j in (x,n):
        if S[j][1:] < S[minj][1:]:
            minj = j
    if minj != x:
        S[x], S[j] = S[j], S[x]

for i in range(1, N):
    v = C[i]
    j = i - 1
    while(j >=0 and C[j] > v):
        C[j+1] = C[j]
        j -= 1
    C[j+1] = v

if(C == B):
    print(" ".join(b for b in B))
    print("Stable")
else:
    print(" ".join(b for b in B))
    print("Not stable")


if(C == S):
    print(" ".join(b for b in S))
    print("Stable")
else:
    print(" ".join(b for b in S))
    print("Not stable")

### FIXED CODE ###

N = int(input())

C = input().split()

B = C[:]
S = C[:]

# bubble sort
flag = 1
while(flag):
    flag = 0
    for x in range(1, N):
        if B[x][1:] < B[x-1][1:]:
            B[x], B[x-1] = B[x-1], B[x]
            flag = 1

# sectionSot
for x in range(0,N):
    minj = x
    for j in range(x,N):
        if S[j][1:] < S[minj][1:]:
            minj = j
    if minj != x:
        S[x], S[minj] = S[minj], S[x]



print(" ".join(b for b in B))
print("Stable")


if(B == S):
    print(" ".join(b for b in S))
    print("Stable")
else:
    print(" ".join(b for b in S))
    print("Not stable")
import math

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

print(math.ceil(mean([a,b])))


### FIXED CODE ###

import math
import statistics as st

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

print(math.ceil(st.mean((a,b))))
S=int(input())
K=int(input())

a=[]
while S !=0:
  s=S%10
  a.append(s)
  S //=10
m=0

for i in range(1,len(a)+1):
  if a[-i]!=1:
    ans=i
    break

print(a[-ans])

### FIXED CODE ###

S=int(input())
K=int(input())

a=[]
while S !=0:
  s=S%10
  a.append(s)
  S //=10
m=0

for i in range(1,len(a)+1):
  if a[-i]!=1:
    if i>K:
      ans=1
    else:
      ans=i
    break
  else:
    ans=1

print(a[-ans])
def examD():
    n = I(); s = I()
    ans = -1
    if s==n:
        ans = n+1
    else:
        loop = int(n**(0.5))
        for b in range(2,loop+1):
            cur = n
            ansC = 0
            while cur>0:
                ansC += cur%b
                cur = cur//b
            if ansC==s:
                ans = b
                break
    if ans==-1:
        for p in range(loop,0,-1):
            bcandi = (n-s)//p + 1
            ansC = n%bcandi + n//bcandi
            if ansC==s:
                ans = int(bcandi)
                break
    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


### FIXED CODE ###

def examD():
    def f(b, n):
        if n < b:
            return n
        else:
            return f(b, n // b) + n % b
    n = I(); s = I()
    ans = -1
    if s==n:
        ans = n+1
    else:
        loop = int(n**(0.5))
        for b in range(2,loop+1):
            if f(b,n)==s:
                ans = b
                break
    if ans==-1:
        for p in range(loop+1,0,-1):
            b = (n-s)//p + 1
            if b >= 2 and f(b,n)==s:
                    ans = b
                    break

    print(ans)

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()
N=2*10**5+2
mod=10**9+7
f=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(1,N):
  fi[i]=pow(f[i],mod-2,mod)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k,n)):
  ans+=f[n]*fi[k]%mod*fi[k]%mod*f[n+1]*%mod*fi[i-1]%mod
  ans%=mod
print(ans)

### FIXED CODE ###

N=2*10**5+1
mod=10**9+7
f=[None]*N
fi=[None]*N
f[0]=1
for i in range(1,N):
  f[i]=i*f[i-1]%mod
for i in range(N):
  fi[i]=pow(f[i],mod-2,mod)
def com(n,k):
  return f[n]*fi[n-k]%mod*fi[k]%mod
def hcom(n,k):
  return com(n+k-1,n-1)
n,k=map(int,input().split())
ans=1
for i in range(1,min(k+1,n)):
  ans=(ans+com(n,i)*hcom(n-i,i)%mod)%mod
print(ans)
N = int(input())
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
A = [A1,A2]
# ここまでが入力

l = []
# 経路の選び方は i に関して
# i回右に進む
# 1回下に進む
# N-i-1回右に進む
# つまり、上の行の[0]~[i]までを加算
# 下の行の[i]~[N]を加算すればいいだけである
for i in range(N):
    counter = 0
    for j in range(i+1):
        counter += A1[j]
    for j in range(i, N):
        counter += A2[j]
    l.append(counter)

print(max(l))

### FIXED CODE ###

# 累積和の手法をとる
# 簡単にいうと要素が ある区間の和 であるようなリストを先に作成しておき
# 必要な時に取り出すという手法である
# 同じ計算過程を何回も繰り返す（上の解法）ことなく結果がでる
N = int(input())
S = input()
w = [0 for _ in range(N)]       # Wを向いている人の番号に１、逆の方角の人に０を割り当てる
sw = [0 for _ in range(N+1)]    # リストwの累積和のリスト、つまり sw[i] は 0~i-1 でWを向いている人の累積和
e = [0 for _ in range(N)]       # Eを向いている人の番号に１、逆の方角の人に０を割り当てる
se = [0 for _ in range(N+1)]    # リストeの累積和のリスト
l = []

for i in range(N):
    if S[i] == "W":
        w[i] = 1
    else:
        e[i] = 1

# 累積和を格納したリストを求める
for i in range(N):
    sw[i+1] = sw[i] + w[i]
    se[i+1] = se[i] + e[i]

# 本計算
for i in range(N):      # i 番目がリーダーだとする
    counter = sw[i] + (se[N] - se[i+1])
    l.append(counter)

print(min(l))
n=int(input())
print(n//500 * 1000 + x//5 * 5)

### FIXED CODE ###

n=int(input())
print(n//500 * 1000 + (n%500)//5 * 5)
n,m=map(int(input().split())
a=list(map(int,input().split()))
if n>=sum(a):
  print(n-sum(a))
else:
  print(-1)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
if n>=sum(a):
  print(n-sum(a))
else:
  print(-1)
S = input()
sum01 = 0
sum10 = 0

for i in range(len(S)):
  if (i % 2) == 0:
    if S[i:i+1] == 1:
      sum01 += 1
  if (i % 2) == 1:
    if S[i:i+1] == 0:
      sum01 += 1

for i in range(len(S)):
  if (i % 2) == 0:
    if S[i+:i+1] == 0:
      sum10 += 1
  if (i % 2) == 1:
    if S[i:i+1] == 1:
      sum10 += 1
        
if sum01 > sum10:
  print(sum10)
else:
  print(sum01)


### FIXED CODE ###

S = input()
sumi = 0
sumii = 0

for i in range(len(S)):
  if (i % 2) == 0:
    if S[i:i+1] == "1":
      sumi += 1
  if (i % 2) == 1:
    if S[i:i+1] == "0":
      sumi += 1

for i in range(len(S)):
  if (i % 2) == 0:
    if S[i:i+1] == "0":
      sumii += 1
  if (i % 2) == 1:
    if S[i:i+1] == "1":
      sumii += 1
        
if sumi > sumii:
  print(sumii)
else:
  print(sumi)
n=int(input())
for i in range(n):
    s=list(str(input()))
m=int(input())
for j in range(m):
    t=list(str(input()))

for i in range(n):
    result=s.count(s[i])-t.count(s[i])

print(max(o,result))

### FIXED CODE ###

n=int(input())
s=[input() for _ in range(n)]
m=int(input())
t=[input() for _ in range(m)]
result=0
for i in set(s):
    result=max(result,s.count(i)-t.count(i))
print(result)
N,A,B = map(int,input().split())
a = N//(A+B)
ans = a*A
ans2 = min(N-(A+B)*a,A)
print(ans+ans2)

### FIXED CODE ###

s = input()
if s[0] == s[1] and s[1] == s[2]:
    print("No")
else:
    print("Yes")
S = input()
K = int(input())
if K == 1:
    print(S[0])
elif S[K] == "1":
    print(1)
else:
    for i in range(len(S)):
        if S[i] != "1":
            print(S[i])
            exit()


### FIXED CODE ###

S = input()
K = int(input())
if K == 1:
    print(S[0])
    exit()
else:
    for i in range(K):
        if S[i] != "1":
            print(S[i])
            exit()
print(1)
int(x)=input()

if x>=30:
    print('Yes')
else:
    print("No")

### FIXED CODE ###

x=input()
x=int(x)
if x>=30:
    print('Yes')
else:
    print("No")
port numpy as np

N=int(input())
A=list(map(int,input().split()))
Q=int(input())

npdata = np.arange(10**5+1)

kosuu=np.zeros(10**5+1)
kosuumoto=kosuu
for i in range(N):
    a=A[i]
    kosuu[a]+=1

BC_list=[]

for i in range (Q):
    bc=list(map(int,input().split()))
    BC_list.append(bc)
S=0
for i in range(Q):
    b=BC_list[i][0]
    c=BC_list[i][1]
    kosuu[c]=kosuu[c]+kosuu[b]
    kosuu[b]=0
    S=sum(np.multiply(npdata,kosuu))
    print(int(S))

    


### FIXED CODE ###


import numpy as np

N=int(input())
A=list(map(int,input().split()))
Q=int(input())

npdata = np.arange(10**5+1)

kosuu=np.zeros(10**5+1)
kosuumoto=kosuu
for i in range(N):
    a=A[i]
    kosuu[a]+=1
SUM=sum(A)

BC_list=[]

for i in range (Q):
    bc=list(map(int,input().split()))
    BC_list.append(bc)
S=SUM
for i in range(Q):
    b=BC_list[i][0]
    c=BC_list[i][1]
    minus=b*kosuu[b]
    plus=c*kosuu[b]
    kosuu[c]=kosuu[c]+kosuu[b]
    kosuu[b]=0
    S=S-minus+plus
    print(int(S))
import collections

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = N
pq = []

for i in range(N):
  for j in range(i+1, N):
    pq.append((xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]))
c = collections.Counter(pq)
ans -= c.most_common()[0][1]
print(ans)

### FIXED CODE ###

import collections

N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]
ans = N
if N == 1:
  print(1)
  exit()
pq = []

for i in range(N):
  for j in range(N):
    pq.append((xy[j][0]-xy[i][0], xy[j][1]-xy[i][1]))
c = collections.Counter(pq)
if c.most_common()[0][0] == (0,0):
  ans -= c.most_common()[1][1]
else:
  ans -= c.most_common()[0][1]
print(ans)
from queue import Queue
import itertools
import numpy as np

R, C = map(int, input().split())
sy, sx = 1, 1
gy, gx = R, C

field = [["#"] * (C + 2)] + \
        [list("#" + input() + "#") for i in range(R)] + \
        [["#"] * (C + 2)]
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
flg = False
cnt = 0

field_1d = list(itertools.chain.from_iterable(field))
field01 = [1 if i == '.' else 0 for i in field_1d]
dot_num = np.array(field01).sum()

q = Queue()
q.put([sy, sx])
field[sy][sx] = 0

while flg == False:
    yx = q.get()
    cnt = field[yx[0]][yx[1]]
    for dy, dx in dxy:
        y_n, x_n = yx[0] + dy, yx[1] + dx
        if y_n == gy and x_n == gx:
            field[y_n][x_n] = cnt + 1
            flg = True
            print(dot_num - (cnt+2))
            break
        if field[y_n][x_n] == '#':
            continue
        if field[y_n][x_n] == '.':
            q.put([y_n, x_n])
            field[y_n][x_n] = cnt + 1
    if flg:
        break
if flg == False:
    print(-1)

### FIXED CODE ###

from collections import deque
 
 
def dfs(field):
    q = deque([(0, 0, 0)])
    visited = [[False] * w for _ in range(h)]
    while q:
        i, j, d = q.popleft()
        if i == h - 1 and j == w - 1:
            return d
        if visited[i][j]:
            continue
        visited[i][j] = True
        if i > 0 and field[i - 1][j] == '.':
            q.append((i - 1, j, d + 1))
        if i < h - 1 and field[i + 1][j] == '.':
            q.append((i + 1, j, d + 1))
        if j > 0 and field[i][j - 1] == '.':
            q.append((i, j - 1, d + 1))
        if j < w - 1 and field[i][j + 1] == '.':
            q.append((i, j + 1, d + 1))
    else:
        return -1
 
 
h, w = map(int, input().split())
field = [input() for _ in range(h)]
dot_cnt = sum(r.count('.') for r in field)
d = dfs(field)
if d == -1:
    print(-1)
else:
    print(dot_cnt - (d+1))
n=int(input())
s=input()
count=0
for i in range(n):
    if s[i]=="A":
        if s[i+1]=="B":
            if s[i+2]=="C":
                count+=1
print(count)


### FIXED CODE ###

n=int(input())
s=input()
count=0
for i in range(n):
    if s[i]=="A":
        if i+1<n and s[i+1]=="B":
            if i+2<n and s[i+2]=="C":
                count+=1
print(count)
3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

### FIXED CODE ###

def gauss_jordan(bs):
    rank = 0
    pivot_cols = []
    for col in reversed(range(61)):
        pivot = -1
        for i,row in enumerate(bs[rank:]):
            if row&(1<<col):
                pivot = rank+i
                break
        if pivot < 0: continue
        pivot_cols.append(col)
        bs[pivot],bs[rank] = bs[rank],bs[pivot]
        for i,row in enumerate(bs):
            if i != rank and row&(1<<col):
                bs[i] ^= bs[rank]
        rank += 1
    return bs

def solve():
    N = int(input())
    A = list(map(int,input().split()))
    S = input()
    bs = []
    for a,s in zip(A[::-1],S[::-1]):
        x = a
        for b in bs:
            x = min(x, x^b)
        if x:
            if s=='0':
                bs.append(x)
                bs = gauss_jordan(bs)
            else:
                return 1
    return 0

T = int(input())
for _ in range(T):
    print(solve())
[a, b] = [int(input()) for _ in range(2)]
print(a*b + " " + (a+b)*2)

### FIXED CODE ###

[a, b] = map(int, input().split())
print(a*b, (a+b)*2)
a, b, c, x = [int(input()) for _ in range(4)]
ans = 0

for i in range(a+1):
  for j in range(b+1):
    for k in range(c+1):
      if 500*a+100*b+50*c == x:
        ans += 1
prit(ans)

### FIXED CODE ###

a, b, c, x = [int(input()) for _ in range(4)]
ans = 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:
        ans += 1
print(ans)
S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ

L = len(S) - 1
mem = [[-1 for _ in range(13)] for _ in range(len(S))]


def calc(i, m):  # i桁目以下で余りがmとなるようにする
    if mem[i][m] >= 0:
        return mem[i][m]
    t = S[L - i]
    if t == '?':
        if i == 0:
            if m < 10:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += calc(i - 1, tm)
            mem[i][m] = s
            return s
    else:
        tn = int(t)
        if i == 0:
            if m == tn:
                mem[i][m] = 1
                return 1
            else:
                mem[i][m] = 0
                return 0
        else:
            tm = m - ((Ls[i % 6] * tn) % 13)
            if tm < 0:
                tm += 13
            k = calc(i - 1, tm)
            mem[i][m] = k
            return k


print(calc(len(S) - 1, 5) % (10 ** 9 + 7))

### FIXED CODE ###

S = input()
Ls = [1, 10, 9, 12, 3, 4]  # 10^n % 13, n % 6でループ
C = 10 ** 9 + 7

L = len(S) - 1
mem = [[0 for _ in range(13)] for _ in range(len(S))]
if S[L] == '?':
    for m in range(10):
        mem[0][m] = 1
else:
    mem[0][int(S[L])] = 1

for i in range(1, len(S)):
    t = S[L - i]
    for m in range(13):
        if t == '?':
            s = 0
            for j in range(10):
                tm = m - ((Ls[i % 6] * j) % 13)
                if tm < 0:
                    tm += 13
                s += mem[i - 1][tm]
            mem[i][m] = s % C
        else:
            tm = m - ((Ls[i % 6] * int(t)) % 13)
            if tm < 0:
                tm += 13
            mem[i][m] = mem[i - 1][tm] % C
print(mem[len(S) - 1][5])