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

from collections import deque
import copy
def solve(maze, start, end):
  memo = []
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
memo = [[False]*(W+2) for _ in range(H+2)]
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    for ey in range(sy, H+1):
      for ex in range(sx+1 if sy == ey else 1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]


def f(i, j):
    t = [[-1] * W for _ in range(H)]
    t[i][j] = 0
    q = [(i, j)]
    while q:
        y, x = q.pop(0)
        if y - 1 >= 0 and S[y - 1][x] != '#' and t[y - 1][x] == -1:
            t[y - 1][x] = t[y][x] + 1
            q.append((y - 1, x))
        if y + 1 < H and S[y + 1][x] != '#' and t[y + 1][x] == -1:
            t[y + 1][x] = t[y][x] + 1
            q.append((y + 1, x))
        if x - 1 >= 0 and S[y][x - 1] != '#' and t[y][x - 1] == -1:
            t[y][x - 1] = t[y][x] + 1
            q.append((y, x - 1))
        if x + 1 < W and S[y][x + 1] != '#' and t[y][x + 1] == -1:
            t[y][x + 1] = t[y][x] + 1
            q.append((y, x + 1))
    return max(max(tt) for tt in t)


result = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '#':
            result = max(result, f(i, j))
print(result)
### BUGGY CODE ###


n = int(input())

ans = 0
count = 0

a, b, c = 1, 1, 1

while a <= n:

    # print("A : {0}".format(a))

    while a * b < n:

        # print("B : {0}".format(b))

        ans += 1

        # if c >= n - (a * b) :
        #     ans += 1

        # while a * b + c <= n:

        #     # print("C : {0}".format(c))

        #     count += 1

        #     if a * b + c == n :
        #         ans += 1

        #     c += 1

        b += 1
        c = 1

    a += 1
    b, c = 1, 1

# print("計算実行回数 : {0}".format(count))
print(ans)

### FIXED CODE ###


n = int(input())

ans = 0
count = 0

a, b, c = 1, 1, 1

while a <= n:

    # print("A : {0}".format(a))
    # print("追加パターン : {0}".format( (n // a) ))

    if a == 1 :
        ans =  ans + ( (n // a) - 1)
    else :

        if n // a == 1 :
            ans = ans + 1
        else :

            if n % a == 0 :
                ans = ans + ( (n // a) - 1)
            else :
                ans = ans + ( (n // a) )

            



    # if n % a == 0 :
    #     ans = ans + ( (n / a) - 1 )
    # else :
    #     ans = ans + ( (n // a) - 1 )

    # ans = ans + (n / a) - 1

    # print("A : {0}".format(a))

    # while a * b < n:

    #     print("B : {0}".format(b))

    #     ans += 1

    #     b += 1
    #     c = 1

    a += 1
    b, c = 1, 1

# print("計算実行回数 : {0}".format(count))
print(ans - 1)
### BUGGY CODE ###

import sys
import numpy as np

N,M,Q=map(int,input().split())

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l][r]+=1

x=np.cumsum(x,axis=0)
x=np.cumsum(x,axis=1)
for _ in range(Q):
    p,q=map(int,input().split())
    print(x[q][q]-x[q][p-1]-x[p-1][q]+x[p-1][p-1])

### FIXED CODE ###

import sys
import numpy as np

input=sys.stdin.readline

N,M,Q=map(int,input().split())

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l,r]+=1

x=np.cumsum(x,axis=0)
x=np.cumsum(x,axis=1)
for _ in range(Q):
    p,q=map(int,input().split())
    print(x[N,q]-x[p-1,q])
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
M = 1
for i in L:
  M *= i
if M > 10**18:
  print(-1)
else:
  print(M)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
M = 1
for i in L:
  M *= i
  if M > 10**18:
    M = -1
    break
print(M)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j])
            isWhite[i][j] = False

res = 0
while queue:
    nextQueue = deque([])
    for pos in queue:
        if pos[0] > 0 and isWhite[pos[0]-1][pos[1]]:
            nextQueue.append([pos[0]-1,pos[1]])
            isWhite[pos[0]-1][pos[1]] = False
        if pos[0] < h-1 and isWhite[pos[0]+1][pos[1]]:
            nextQueue.append([pos[0]+1,pos[1]])
            isWhite[pos[0]+1][pos[1]] = False
        if pos[1] > 0 and isWhite[pos[0]][pos[1]-1]:
            nextQueue.append([pos[0],pos[1]-1])
            isWhite[pos[0]][pos[1]-1] = False
        if pos[1] < w-1 and isWhite[pos[0]][pos[1]+1]:
            nextQueue.append([pos[0],pos[1]+1])
            isWhite[pos[0]][pos[1]+1] = False
            
#        print(queue)
    queue = nextQueue
    res += 1
print(res-1)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

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


import heapq
from collections import defaultdict, deque
# from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ----------

H, W, K = mii()
S = []
for i in range(H):
    S.append(si())

ans = INF
for div in range(1<<(H-1)):
    id = [0] * H
    g = 0
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1

    c = [[0] * W for _ in range(g+1)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                c[id[i]][j] += 1

    now = defaultdict(int)

    def add(j):
        for i in range(g+1):
            now[i] += c[i][j]
        for i in range(g+1):
            if now[i] > K:
                return False
        return True

    num = g
    for j in range(W):
        if not add(j):
            num += 1
            now = defaultdict(int)
            if not add(j):
                num = INF
                break

    ans = min(ans, num)

print(ans)



### FIXED CODE ###


import heapq
from collections import defaultdict, deque
# from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
import bisect


sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))
# ----------

H, W, K = mii()
S = []
for i in range(H):
    S.append(si())

ans = INF
for div in range(1<<(H-1)):
    id = [0] * H
    g = 0
    for i in range(H):
        id[i] = g
        if div >> i & 1:
            g += 1

    c = [[0] * W for _ in range(g+1)]

    for i in range(H):
        for j in range(W):
            if S[i][j] == '1':
                c[id[i]][j] += 1

    now = defaultdict(int)

    def add(j):
        for i in range(g+1):
            now[i] += c[i][j]
        for i in range(g+1):
            if now[i] > K:
                return False
        return True

    num = g
    for j in range(W):
        if not add(j):
            num += 1
            now = defaultdict(int)
            if not add(j):
                num = INF
                break

    ans = min(ans, num)

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

from sys import stdin

def main():
    n, m, k = [int(x) for x in stdin.readline().rstrip().split()]

    pileda = 0
    a = [0]
    # ai = 0
    for x in stdin.readline().rstrip().split():
        # ai += 1
        x = int(x)
        pileda += x
        a.append(pileda)
        if pileda > k:
            break
    
    piledb = 0
    b = [0]
    for x in stdin.readline().rstrip().split():
        x = int(x)
        piledb += x
        b.append(piledb)
        if piledb > k:
            break

    ans = 0
    for ai, time_a in enumerate(a):
        for bi, time_b in enumerate(b):
            if time_a + time_b > k:
                break
            if time_a + time_b <= k and ai + bi > ans:
                ans = ai + bi
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

def main():
    n, m, k = [int(x) for x in stdin.readline().rstrip().split()]

    pileda = 0
    a = [0]
    for x in stdin.readline().rstrip().split():
        x = int(x)
        pileda += x
        a.append(pileda)
    
    piledb = 0
    b = [0]
    for x in stdin.readline().rstrip().split():
        x = int(x)
        piledb += x
        b.append(piledb)

    ans = 0
    bi = m
    for ai, at in enumerate(a):
        if at > k:
            break

        while at + b[bi] > k:
            bi -= 1
        
        ans = max(ans, ai+bi)
    
    print(ans)
            

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

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(n):
	num,num2 = 1,1
	for j in range(i+1,n):
		if a[j]>a[i]: num+=1
		else: break
	for j2 in range(i-1,-1,-1):
		if a[j2]>a[i]: num2+=1
		else: break
	ans += a[i]*num*num2
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b,l,r,ans = [0]*(n+1),[i for i in range(n+2)],[i for i in range(n+2)],0
for i in range(n): b[a[i]]=i
for i in range(n,0,-1):
	m = b[i]
	x,y = l[m],r[m]
	ans+=i*(m-x+1)*(y-m+1)
	l[y+1],r[x-1] = x,y
print(ans)
### BUGGY CODE ###

#ABC154D
import sys

n, k = map(int, sys.stdin.readline().split())
p = list(map(int, sys.stdin.readline().split()))
L = [0 for _ in range(n)]

total = 0
idx = 0
for i in range(n+1-k):
    tmp = sum(p[i:i+k])
    if total < tmp:
        total = tmp
        idx = i

ans = 0
for i in range(k):
    ans +=(1 + p[idx + i])/2

print(ans)

### FIXED CODE ###

#ABC154D
import sys
N, K = map(int, sys.stdin.readline().split())
P = list(map(int, sys.stdin.readline().split()))

#print(P)

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2
#print(L)

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

#print(S)
total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)
### BUGGY CODE ###

x, y = map(int, input().split())
m = max(x, y) % min(x, y)

if m == 0:
    print(min(x, y))
else:
    for d in range(m-1, 0, -1):
        if min(x, y) % d ==0 and m % d ==0:
            print(d)
            break

### FIXED CODE ###

def gcd(b, s):
    mod = b % s
    if mod != 0:
        return gcd(s, mod)
        
    else:
        return s

x, y = map(int, input().split())
b = max(x, y)
s = min(x, y)
a = gcd(b, s)
print(a)
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
s = [0]*(10**6+1)
t = [0]*169
u = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
     101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
     211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
     307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
     401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
     503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
     601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
     701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
     809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
     907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
v = 0
m = 169
for i in range(n):
    for j in range(m):
        if(a[i]%u[j] == 0):
            t[j] += 1
            while(a[i]%u[j] == 0):
                a[i] //= u[j]
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s[a[i]] += 1
        v += 1
x = max(t)
y = max(s)
if(x == n):
    print('not coprime')
elif(x <= 1):
    z = 0
    if(v > 0):
        if(y <= 1):
            print('pairwise coprime')
        else:
            print('setwise coprime')    
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

from collections import deque

n = int( input( ) )
que = deque( )
for i in range( n ):
	op = input( ).split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )

print( " ".join( que ) )

### FIXED CODE ###

import sys
from collections import deque

n = int( sys.stdin.readline( ) )
que = deque( )
lines = sys.stdin.readlines()
for line in lines:
	op = line.rstrip().split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )


print( " ".join( que ) )
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    k = int(input())
    if k%2 == 0:
        print(-1)
        sys.exit()
    cnt = 1
    a = 7
    while a<10**100000+1:
        if a%k == 0:
            print(cnt)
            sys.exit()
        a*=10
        a+=7
        cnt+=1
    print(k-1)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    k = int(input())
    if k%2 == 0:
        print(-1)
        sys.exit()
    cnt = 1
    a = 7
    d = [a]
    for i in range(10**6+1):
        if d[i]%k == 0:
            print(i+1)
            sys.exit()
        b = 10*d[i]
        b%=k
        b+=7
        b%=k
        d.append(b)
    print(-1)
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
L = sorted(L,reverse=True)
total = 0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        if L[j] >= L[i]/2:
            for k in range(j+1,n):
                if L[j] + L[k] > L[i]:
                    total += 1
                else:
                    break
        else:
            break
print(total)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int,input().split()))
L = sorted(L)
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        limit = L[i]+L[j]
        ans += bisect.bisect_left(L,limit) - (j+1)

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

S = input()
n = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        for num in range(10):
            for j in range(13):
                dp[i+1][(j*10+num)%13] += dp[i][j]
    else:
        num = int(S[i])
        for j in range(13):
            dp[i + 1][(j * 10 + num) % 13] += dp[i][j]

    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[n][5])

### FIXED CODE ###

S = input()
n = len(S)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    if S[i] == '?':
        for num in range(10):
            for j in range(13):
                dp[i+1][(j*10+num)%13] += dp[i][j]
    else:
        num = int(S[i])
        for j in range(13):
            dp[i + 1][(j * 10 + num) % 13] += dp[i][j]

    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[n][5])
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
c=[0]*N
for i in A:
  c[i-1]+=1
for a in c:
  print(a)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
  print(str(int(A.index(i))+1) + ' ', end = '')

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
D = [0]*N
for i in range(N):
  a = A[i]
  D[a-1] = i+1
d = str(D[0])
for i in range(1,N):
  d += ' '+str(D[i])
print(d)
### BUGGY CODE ###

def resolve():
    K, S = map(int, input().split())
    print(
        len(
            [
                (x, y, z)
                for x in range(K + 1)
                for y in range(K + 1)
                for z in range(K + 1)
                if x + y + z == S and max(x, y, z) <= K
            ]
        )
    )


if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    K, S = map(int, input().split())
    count = 0
    for x in range(K + 1):
        for y in range(K + 1):
            if S - K <= x + y <= S and max(x, y) <= K:
                count += 1
    print(count)


if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

S=input()
keta=len(S)
dp=[[0 for j in range(13)] for i in range(keta)]
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
def convert(bef,add):
  nex=bef+add
  if nex>=13:
    nex-=13
  return nex
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i][convert(j,k*dig%13)]+=dp[i-1][j]
        dp[i][convert(j,k*dig%13)]%=DIV
  else:
    ch=int(S[keta-1-i])
    for j in range(13):
      dp[i][convert(j,ch*dig%13)]+=dp[i-1][j]
      dp[i][convert(j,ch*dig%13)]%=DIV

print(dp[len(dp)-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###

n = int(input())
ans = 0

def max(a,b):
    if a>b:
        return a
    else:
        return b

def min(a,b):
    if a<b:
        return a
    else:
        return b

def gcd(a,b):
    p = max(a,b)
    q = min(a,b)
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d


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

print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
 
def max(a,b):
    if a>b:
        return a
    else:
        return b
 
def min(a,b):
    if a<b:
        return a
    else:
        return b
 
def gcd(a,b):
    p = max(a,b)
    q = min(a,b)
    d = q
    while p % q != 0:
        d = p % q
        p = q
        q = d
    return d
 
 
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans += gcd(gcd(i,j),k)
 
print(ans)
### BUGGY CODE ###

# input
A, B, C, K = map(int, input().split())

# check
result_score = 0
while K > 0:
        for score, i in [(1, A), (0, B), (-1, C)]:
                while K > 0 and i > 0:
                        result_score += score
                        i -= 1
                        K -= 1

print(result_score)

### FIXED CODE ###

# input
A, B, C, K = map(int, input().split())

# check
result_score = 0
for score, i in [(1, A), (0, B), (-1, C)]:
        if K <= 0:
               continue

        if K >= i:
            result_score += score * i
            K -= i
        else:
            result_score += score * K
            K = 0

print(result_score)
### BUGGY CODE ###

from bisect import bisect_left
import copy
from itertools import combinations


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

li = list(combinations(l, 2))


ans = 0
for i in li:
    x = copy.deepcopy(l)
    x.remove(i[0])
    x.remove(i[1])
    left = abs(i[0] - i[1])
    small = min(i[0], i[1])
    x = [i for i in x if i < small]

    if len(x) != 0:
        left_div = bisect_left(x, left+1)
        ans += max(0, len(x) - left_div)

print(ans)

### FIXED CODE ###

from bisect import bisect_left
import copy

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


ans = 0
for small in range(n - 2):
    for mid in range(small + 1, n - 1):
        div = bisect_left(l, l[small] + l[mid], 0, n)
        if div > mid + 1:
            ans += div - mid - 1

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

n=int(input())
poll=[input() for i in range(n)]

dic={}
for string in poll:
  if string not in dic:
    dic[string]=1
  else:
    dic[string]+=1

max_k=[k for k, v in dic.items() if v == max(dic.values())]
max_k.sort() 
print(*max_k,sep='\n')

### FIXED CODE ###

def main():
  n=int(input())
  poll=[input() for i in range(n)]

  dic={}
  for string in poll:
    if string not in dic:
      dic[string]=1
    else:
      dic[string]+=1
  
  x=max(dic.values()) 
  max_k=[k for k, v in dic.items() if v==x]
  max_k.sort()
  print(*max_k,sep='\n')
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

N,Q = (int(i) for i in input().split())  
S = input()
for _ in range(Q):
    l,r = (int(i) for i in input().split())  
    s = S[l-1:r]
    count = 0
    for i in range(len(s) - 1):
        if s[i] + s[i+1] == 'AC':
            count += 1
    print(count)

### FIXED CODE ###

N,Q = (int(i) for i in input().split())  
S = input()
AC_count = [0] * N
for i in range(1,N):
    AC_count[i] = AC_count[i - 1]
    if S[i - 1] + S[i] == 'AC':
        AC_count[i] += 1

for _ in range(Q):
    l,r = (int(i) for i in input().split())
    ans = AC_count[r-1] - AC_count[l-1] 
    print(ans)