Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
import random
import itertools
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
h, w = map(int,input().split())
a = [[j for j in input()] for i in range(h)]
def osen(x,y):
    global kuro2
    if x >0 and a[x-1][y] == ".":
        kuro2.append([x-1,y])
        a[x-1][y] = "#"
    if x < h-1 and a[x+1][y] == ".":
        kuro2.append([x+1,y])
        a[x+1][y] = "#"       

    if y >0 and a[x][y-1] == ".":
        kuro2.append([x,y-1])
        a[x][y-1] = "#"
    if y < w-1 and a[x][y+1] == ".":
        kuro2.append([x,y+1])
        a[x][y+1] = "#"      



kuro = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            kuro.append([i,j])
ans = 0
while kuro:
    kuro2 = []
    while kuro:
        x,y = kuro.pop()
        osen(x,y)
    kuro = kuro2
    ans += 1

print(ans-1)

### FIXED CODE ###

import sys
import random
import itertools
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
h, w = map(int,input().split())
a = [[j for j in input()] for i in range(h)]
def osen(x,y):
    global kuro2
    if x >0 and a[x-1][y] == ".":
        kuro2.append([x-1,y])
        a[x-1][y] = "#"
    if x < h-1 and a[x+1][y] == ".":
        kuro2.append([x+1,y])
        a[x+1][y] = "#"       

    if y >0 and a[x][y-1] == ".":
        kuro2.append([x,y-1])
        a[x][y-1] = "#"
    if y < w-1 and a[x][y+1] == ".":
        kuro2.append([x,y+1])
        a[x][y+1] = "#"      



kuro = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            kuro.append([i,j])
ans = 0
while kuro:
    kuro2 = []
    while kuro:
        x,y = kuro.pop()
        osen(x,y)
    kuro = kuro2
    ans += 1

print(ans-1)
### BUGGY CODE ###

n = int(input())
s = input()
hs = [ int(i) for i in s.rsplit() ]

max = 0
for i in range(len(hs)):
    lmax = 0
    for k in range(1, len(hs)-i):
        if hs[i+k] <= hs[i+k-1]:
            lmax = lmax + 1
        else:
            break

        if lmax > max:
            max = lmax

print(max)

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))

count = 0
count_list = [0]

for i in range(n-1):
	if(h[i+1] <= h[i]):
		count += 1
		count_list.append(count)
	else:
		count = 0

print(max(count_list))
### BUGGY CODE ###

n=int(input())
def count_divisor(n):
    i, count = 1, 0
    while i * i <= n:
        if n % i == 0:
            if i * i == n:
                count += 1
            else:
                count += 2
        i += 1
    return count
ans=0
for k in range(1,n+1):
    ans+=k*count_divisor(k)
print(ans)

### FIXED CODE ###

N=int(input())
ans=(N*(N+1))//2  #1の時
for i in range(2,N+1):
  m=N//i
  ans+=i*(m*(m+1)//2)
print(ans)
### BUGGY CODE ###

S=list(input())

B=[]
for i in range(len(S)):
    B.append(0)

for i in range(len(S)):
    if S[i]=='R':
        r=i+1
        while S[r]=='R':
            r+=1
        if (r-i)%2==1:
            B[r-1]+=1
        else:
            B[r]+=1

    if S[i]=='L':
        l=i-1
        while S[l]=='L':
            l-=1
        if (l+i)%2==1:
            B[l+1]+=1
        else:
            B[l]+=1

print(' '.join(map(str,B)))


### FIXED CODE ###

S=list(input())
N=len(S)

B=[0]*len(S)

s=0
for i in range(N):
    if S[i]=='R':
        s+=1
    else:
        if s%2==1:
            B[i]+=int((s-1)/2)
            B[i-1]+=int((s-1)/2+1)
        else:
            B[i]+=int(s/2)
            B[i-1]+=int(s/2)
        s=0

s=0
for i in range(N-1,-1,-1):
    if S[i]=='L':
        s+=1
    else:
        if s%2==1:
            B[i]+=int((s-1)/2)
            B[i+1]+=int((s-1)/2+1)
        else:
            B[i]+=int(s/2)
            B[i+1]+=int(s/2)
        s=0

print(' '.join(map(str,B)))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    from fractions import gcd

    def lcd(x, y):
        g = gcd(x, y)
        return x * y // g
    
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    l = 1
    for e in a:
        l = lcd(l, e)

    ans = 0
    for e in a:
        ans += l // e
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from fractions import gcd


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

print(ans)
### BUGGY CODE ###

h,n = map(int,input().split())
a_list = list(map(int,input().split()))
def part_sum(a,A):
    #初期化
    N = len(a)
    dp = [[0 for i in range(A+1)] for j in range(N + 1)]
    dp[0][0] = 1
    
    #DP
    for i in range(N):
        for j in range(A+1):
            if a[i] <= j :
                dp[i + 1][j] = dp[i][j - a[i]] or dp[i][j]
            else :
                dp[i +1][j] = dp[i][j]
    return dp[N][A]
if part_sum(a_list,h) ==0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

h,n = map(int,input().split())
a_list = list(map(int,input().split()))
if sum(a_list) >= h:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

n = int(input())
d = list(map(int, input().split()))
d_max = max(d)
d_half = len(d) // 2
ans = 0

for i in range(1, d_max+1):
    abc = [x for x in d if x < i]
    if len(abc) == d_half:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
d.sort()

print(d[n//2] - d[n//2-1])
### BUGGY CODE ###

N = int(input())
mod = 10**9+7
ans = 1
for i in range(1,N+1):
    ans *= i
ans %= mod
print(ans)

### FIXED CODE ###

N = int(input())
mod = 10**9+7
ans = 1
for i in range(1,N+1):
    ans *= i
    ans %= mod
# ans %= mod
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    D = []

    for _ in range(N):
        command, value = [i for i in input().split()]

        if command == "insert":
            D.append(value)
        else:
            if value in D:
                print("yes")
            else:
                print("no")

main()



### FIXED CODE ###

import sys
import collections

# Set max recursion limit
sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]


def main():
    N = int(input())
    C = [input().split() for _ in range(N)]

    D = collections.defaultdict(lambda: 0)

    for c in C:
        command, value = c

        if command == "insert":
            D[value] = 1
        else:
            if D[value] == 1:
                print("yes")
            else:
                print("no")


main()
### BUGGY CODE ###

from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]
 
    A = [0]+list(map(int, input().split()))
 
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1
 
    d = deque()
    d.append((1, [0, A[1]]))
 
    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            if dp[-1] < A[i]:
                dp.append(A[i])
                d.append((i, dp.copy()))
                dist[i] = len(dp)-1
                dp.pop()
            else:
                bis = bisect.bisect_left(dp, A[i])
                updatetask=dp[bis]
                dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp.copy()))
                dp[bis]=updatetask
 
    print(*dist[1:], sep="\n")
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    c = [[0]*w for i in range(h)]
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1
        c[x[0]][x[1]] = 1

    my = max(ay)
    mx = max(ax)
    by = [i for i, x in enumerate(ay) if x == my]
    bx = [i for i, x in enumerate(ax) if x == mx]

    ans = my + mx
    tmp = 1
    for y in by:
        for x in bx:
            if c[y][x] == 0:
               tmp = 0
               break
    print(ans - tmp)

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def solve():
    h, w, m = MAP()
    s = [LIST1() for i in range(m)]
    ay = [0]*h
    ax = [0]*w
    for x in s:
        ay[x[0]] += 1
        ax[x[1]] += 1

    my = max(ay)
    mx = max(ax)
    
    by = bx = 0
    for y in ay:
        if y == my:
            by += 1
    for x in ax:
        if x == mx:
            bx += 1
            
    ans = my + mx
    tmp = 0
    for x in s:
        if ay[x[0]]+ax[x[1]]==ans:
            tmp += 1
    if tmp == by*bx:
        ans -= 1
    print(ans)
    
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            tmp = 0
            if i+j+k > 0:
                tmp += n/(i+j+k)
            if i > 0:
                tmp += DP[i-1][j][k]*i/(i+j+k)
            if j > 0:
                tmp += DP[i+1][j-1][k]*j/(i+j+k)
            if k > 0:
                tmp += DP[i][j+1][k-1]*k/(i+j+k)
            DP[i][j][k] = tmp
print(DP[a][b][c])


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

n = int(input())
x = list(map(int, input().split()))
import copy
for i in range(n):
    l1 = copy.copy(x)
    l1.sort()
    l1.remove(x[i])
    print(l1[int((n / 2) - 1)])

### FIXED CODE ###

n = int(input())
x = list(map(int, input().split()))
import copy
l1 = copy.copy(x)
l1.sort()
median1 = l1[int(n / 2) - 1]
median2 = l1[int(n / 2)]
if median1 == median2:
    for i in range(n):
        print(median1)
else:
    for i in range(n):
        if x[i] <= median1:
            print(median2)
        else:
            print(median1)
### BUGGY CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

points = X[:]
points.sort()

if M<=N:
    ans = 0
else:
    import sys
    INT_MAX = sys.maxsize
    ans = INT_MAX

    import itertools
    for v in itertools.combinations(list(range(1, M)),N-1):
        v = list(v)
        v.insert(0,0)
        v.append(M)
        #print(v)
        cost_sum = 0
        for i in range(1, len(v)):
            sub_p = points[v[i-1]:v[i]]
            cost = sub_p[-1] - sub_p[0]
            #print(sub_p, cost)
            cost_sum += cost
            if cost_sum >= ans:
                break
        ans = min(ans, cost_sum)

print(ans)





    




### FIXED CODE ###

N, M = map(int, input().split())
X = list(map(int, input().split()))

if M <= N:
    ans = 0
else:
    points = X[:]
    points.sort()

    diff_p = []
    for i in range(1, len(points)):
        diff_p.append(points[i] - points[i-1])

    diff_p.sort()
    #print(diff_p)

    ans = sum(diff_p[:M-N])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

n=max(A)

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(n+1)
is_prime[0] = False

for i in range(2, n+1):
    if is_prime[i-1]:
        j = 2 * i
        while j <= n:
            is_prime[j-1] = False
            j += i

table = [ i for i in range(1, n+1) if is_prime[i-1]]
#print(table)

lcm=[0]*len(table)
p=[1]*len(table)



for i in range(N):
    for j in range(len(table)):
        a=A[i]
        if a%p[j]==0:
            a=a//p[j]
            while a%table[j]==0:
                a=a//table[j]
                lcm[j]+=1
                p[j]*=table[j]
                
        
l=1
for j in range(len(table)):
    l*=p[j]
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    ans%=mod
    
print(ans%mod)

### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

def main():
  N=int(input())
  P=list(map(int,input().split()))
  sFlag=True
  i=0
  sumCount=0
  while(sFlag):
    Pi=P[i]
    for j in range(0,i+1):
      Pj=P[j]
      if(Pi>Pj):
        break
      if(j==i):
        sumCount=sumCount+1
    i=i+1
    if(i==N):
      sFlag=False
  print(sumCount)
if __name__ == '__main__':
  main()

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))

num = p[0]
ans = 1

for i in range(1, n):
    if num >= p[i]:
        ans += 1
        num = p[i]

print(ans)
### BUGGY CODE ###

n = int(input())
data = [int(x) for x in input().split()]

total = 0
for i in range(n):
    for j in range(i,-1,-1):
        if data[i] > data[j]:
            break
    else:
        total += 1

print(total)


### FIXED CODE ###

n = int(input())
data = [int(x) for x in input().split()]

min_num = data[0]
ans = 0
for i in range(n):
    if min_num >= data[i]:
        ans += 1
        min_num = data[i]

print(ans)
### BUGGY CODE ###

def solve(N, Y):
    for x in range(N, -1, -1):
        for y in range(N - x, -1, -1):
            for z in range(N - x - y, -1, -1):
                if x + y + z == N and 10000 * x + 5000 * y + 1000 * z == Y:
                    return x, y, z
    return -1, -1, -1

N, Y = list(map(int, input().split()))
x, y, z = solve(N, Y)
print('{} {} {}'.format(x, y, z))

### FIXED CODE ###

def solve(N, Y):
    for x in range(N+1):
        for y in range(N+1):
            z = N - x - y
            if z < 0:
                continue
            elif 10000 * x + 5000 * y + 1000 * z == Y:
                return x, y, z
    return -1, -1, -1

N, Y = list(map(int, input().split()))
x, y, z = solve(N, Y)
print('{} {} {}'.format(x, y, z))
### BUGGY CODE ###

N,M = map(int,input().split())
cards = [True]*N

for g in range(M):
  L,R = map(int,input().split())
  for i in range(L-1):
    cards[i] = False
  for i in range(R,N):
    cards[i] = False
print(cards.count(True))

### FIXED CODE ###

N,M = map(int,input().split())
maL = 0
miR = N
for g in range(M):
  L,R = map(int,input().split())
  maL = max(maL,L)
  miR = min(miR,R)
if maL <= miR:
  print(miR-maL+1)
else:
  print(0)
### BUGGY CODE ###

h,w = map(int,input().split())
space = []
for _ in range(h):
    space.append(list(input()))

max_light = 0
for i in range(h):
    for j in range(w):
        if space[i][j] != "#":
            light = 1
            #right
            pos = j+1
            while( pos < len(space[i])):
                if space[i][pos] == ".":
                    light += 1
                    pos += 1
                else:
                    break
            pos = j-1
            while( 0 <= pos ):
                if space[i][pos] == ".":
                    light += 1
                    pos -= 1
                else:
                    break
            pos = i+1
            while(pos < len(space)):
                if space[pos][j] == ".":
                    light += 1
                    pos += 1
                else:
                    break

            pos = i-1
            while( 0 <= pos ):
                if space[pos][j] == ".":
                    light += 1
                    pos -= 1
                else:
                    break
        
            max_light = max(max_light,light)
print(max_light)

### FIXED CODE ###

h,w = map(int,input().split())
space = []
for _ in range(h):
    space.append(list(input()))

light_space = [[1 for i in range(w)] for j in range(h)]
max_light = 0
for i in range(w):
    light = -1
    light_right = -1
    for j in range(h):
        low_point = len(space)-j-1

        if space[j][i] == "#":
            light = -1
            light_space[j][i] = 0
        else:
            light += 1
            light_space[j][i] += light

        if space[low_point][i] == "#":
            light_right = -1
            light_space[low_point][i] = 0
        else:
            light_right += 1
            light_space[low_point][i] += light_right

for j in range(h):
    light = -1
    light_right = -1
    for i in range(w):
        right_point = len(space[j])-i-1

        if space[j][i] == "#":
            light = -1
            light_space[j][i] = 0
        else:
            light += 1
            light_space[j][i] += light
        
        if space[j][right_point] == "#":
            light_right = -1
            light_space[j][right_point] = 0
        else:
            light_right += 1
            light_space[j][right_point] += light_right

        max_light = max(max_light,light_space[j][right_point],light_space[j][i])


print(max_light)
### BUGGY CODE ###

x1 = input()
x2 = [int(s) for s in input().strip().split(" ") ]
 
result =  1
for x in x2:
   result *= x 

if 10**18 < result :
 print(-1)
else:
 print(result) 


### FIXED CODE ###

x1 = input()
x2 = [int(i) for i in input().split(" ")]

result = 0
if 0 in x2:
  None 
else:
  result = 1
  for xv in x2:
     result = xv * result
  
     if 10**18 < result : 
        result = -1
        break


print(result)
### BUGGY CODE ###

n = int(input())
lst = []
for _ in range(n):
  lst.append(int(input()))
for i in range(n):
  temp = lst[:i]+lst[i+1:]
  print(max(temp))

### FIXED CODE ###

import numpy as np

n = int(input())
lst = []
for _ in range(n):
  lst.append(int(input()))
max_idx = np.argmax(lst)
max_ = lst[max_idx]
lst[max_idx] = 0
next_max_ = max(lst)

for i in range(len(lst)):
  if i == max_idx:
    print(next_max_)
  else:
    print(max_)
### BUGGY CODE ###

s = list(input())
if len(s) <= 2:
    print(0)
else:
    i = 2
    ans = 0
    while i < len(s):
        if s[i] == "C" and s[i-1] == "B" and s[i-2] == "A":
            s[i] = "A"
            s[i-1] = "C"
            s[i-2] = "B"
            ans += 1
            i -= 1
        else:
            i += 1
    print(ans)

### FIXED CODE ###

s = input()
s = s.replace("BC", "X")

ans = 0
a_count = 0

for i in range(len(s)):
    if s[i] == "A":
        a_count += 1
    elif s[i] == "X":
        ans += a_count
    else:
        a_count = 0

print(ans)
### BUGGY CODE ###

import numpy as np

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

    a = np.array((list(map(int, input().split()))))

    for i in range(m):
        a[a.argmax()] //= 2
    print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline


def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)


def _heappop_max(heap):
    """Maxheap version of a heappop."""
    lastelt = heap.pop()    # raises appropriate IndexError if heap is empty
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt


def main():
    n, m = map(int, input().split())

    if n == 1:
        a = int(input())
        for i in range(m):
            a //= 2
        print(a)
        exit()

    a = (list(map(int, input().split())))
    heapq._heapify_max(a)

    for i in range(m):
        tmp = _heappop_max(a) // 2
        _heappush_max(a, tmp)

    print(sum(a))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

S=list(input())
l = len(S)
i = 0
j = -1
ans = 0
while i<l:
    if j==-1 and S[i] == "A":
        j=i
        i+=1
    elif j>=0 and S[i] == "A":
        i+=1
    elif j>=0:
        if len(S[i:i+2])==2 and S[i] == "B" and S[i+1] == "C":
            S[i] = "A"
            S[i+1] = "A"
            S[j] = "B"
            S[j+1] = "C"
            ans += i-j
            i = j
            j = -1
        else:
            j = -1
            i+=1
    else:
        i+=1
print(ans)

### FIXED CODE ###

S=input().replace("BC","D").replace("B","C").split("C")
ans = 0
for s in S:
    a = 0
    for c in s:
        if c == "A":a+=1
        else:ans += a
print(ans)
### BUGGY CODE ###

n = int(input())
data = [input() for i in range(n)]
ans = 0
for a in range(n):
    b = 0
    t = True
    for i in range(n):
        for j in range(n):
            if data[(i + a) % n][(j + b) % n] != data[(j + a) % n][(i + b) % n]:
                t = False
                break

    if t:
        ans += n

print(ans)

### FIXED CODE ###

n = int(input())
data = [input() for i in range(n)]
ans = 0
for a in range(n):
    b = 0
    t = True
    for i in range(n):
        for j in range(n):
            if data[(i + a) % n][(j + b) % n] != data[(j + a) % n][(i + b) % n]:
                t = False
                break

    if t:
        ans += n

print(ans)