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

# coding:utf-8

def main():
    N,Q = map(int,input().split())
    S = input()
    for i in range(Q):
        li,ri = map(int,input().split())
        temp = S[li-1:ri]
        # print(temp)
        print(ac_check(temp))


def ac_check(sub_s):
    count = 0
    for i in range(len(sub_s)-1):
        if sub_s[i:i+2] == "AC":
            count += 1
    return count


if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8

memo = []

def main():
    N,Q = map(int,input().split())
    S = input()
    t = [0] *(N+1)
    for i in range(N):
        if S[i:i+2] == "AC":
            t[i+1] = t[i] + 1
        else:
            t[i+1] = t[i]
    # for i in range(N-1):
    #     if S[i:i+2] == "AC":
    #         memo.append(i)
    # print(memo)

    for i in range(Q):
        li,ri = map(int,input().split())
        print(t[ri-1] - t[li-1])
        # count = len(memo)
        # 両方の範囲に入る最初と最後
        # print(li,ri)
        # for i in range(li-1,ri-1):
        #     # print("debug"+str(i))
        #     if S[i] == "A" and S[i+1] == "C":
        #         count += 1
        #         start = i
        #         break
        # if start < 0:
        #     count = 0
        # else: 
        #     for i in reversed(range(li-1,ri+1)):
        #         if S[i-1] == "A" and S[i] == "C":
        #             end = i-1
        #             break
        #     print(start,end)
        #     count = memo.index(end) - memo.index(start) + 1


        # for i in range(len(memo)):
        #     if ac_check(i,li,ri):
        #         start = i
        #         break
        # if start < 0:
        #     count = 0
        # else:
        #     for i in reversed(range(len(memo))):
        #         if ac_check(i,li,ri):
        #             end = i
        #             break
        #     # print(start,end)
        #     count = count - (start) - (len(memo)-end) + 1
        # print(count)

# def ac_check(i,li,ri):
#     if memo[i] >= li-1 and memo[i]+1 <= ri-1:
#         return True
#     return False

# def ac_check(sub_s):
#     count = 0
#     for i in range(len(sub_s)-1):
#         if sub_s[i:i+2] == "AC":
#             count += 1
#     return count


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

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = []
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            rcount += len(left[lpos:])
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count

### FIXED CODE ###

from array import array

def merge_sort(A):
    if len(A) <= 1:
        return A, 0
    mid = len(A) // 2
    left, lcount = merge_sort(A[:mid])
    right, rcount = merge_sort(A[mid:])
    merged, count = merge(left, right)
    return merged, lcount + rcount + count

def merge(left, right):
    lpos = 0
    rpos = 0
    rcount = 0
    merged = array('I', [])  # List is too slow. Use an array instead.
    len_left = len(left)
    len_right = len(right)
    while lpos < len_left and rpos < len_right:
        if left[lpos] < right[rpos]:
            merged.append(left[lpos])
            lpos += 1
        else:
            merged.append(right[rpos])
            rpos += 1
            #rcount += len(left[lpos:])
            rcount += len_left - lpos
    
    if left[lpos:]:
        merged.extend(left[lpos:])
    if right[rpos:]:
        merged.extend(right[rpos:])
    
    return merged, rcount
    
if __name__ == '__main__':
    n = int(raw_input())
    A = array('I', map(int, raw_input().split()))
    
    sorted, count = merge_sort(A)
    #print ' '.join(str(x) for x in sorted)
    print count
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

# 期待値のリスト生成
ex_list = list()
for i in range(len(p)):
	ex_list.append((1+p[i])/2)

ans = 0
for i in range(N-K+1):
	ex = sum(ex_list[i:i+K])
	if ans < ex:
		ans = ex

print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

# 期待値の累積和リストを生成
ex_list = list() 
for i in range(len(p)):
	if i != 0:
		ex_list.append(((1+p[i])/2)+ex_list[-1])
	else:
		ex_list.append((1+p[i])/2)

ans = ex_list[K-1]
for i in range(N-K):
	# print(i,ex_list[i],ex_list[i+K])
	ex = abs(ex_list[i] - ex_list[i+K])
	if ans < ex:
		ans = ex
print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
anslist = []

for i in range(q):
  l,r = map(int,input().split())
  anslist.append(s[l-1:r])
for i in range(q):
  cnt = 0
  for j in range(len(anslist[i])-1):
    if anslist[i][j] == 'A' and anslist[i][j+1] == 'C':
      cnt += 1 
  print(cnt)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split()))for i in range(q)]

a = [0]*n
p = 0
for i in range(1,n):
    if s[i-1] == 'A' and s[i] == 'C':
        p += 1
    a[i] = p
ans = []
for i in range(q):
    ans.append(a[lr[i][1]-1]-a[lr[i][0]-1])
for i in range(q):
    print(ans[i])
### BUGGY CODE ###

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

l=[]
dup=False
for e in A:
    if e in l:
        dup=True
        break
    else:
        l.append(e)

if dup==False:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

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

A.sort()
a=-1
ndup=True
for e in A:
    if a==e:
        ndup=False
    else:
        pass
    a=e
if ndup==True:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

def main():
  n, k = map(int, input().split(' '))
  A = list(range(n+1))
  ans = 0
  for i in range(k, n+2):
    tmp_min = sum(A[:i])
    tmp_max = sum(A[n+1-i:])
    ans += tmp_max - tmp_min + 1
  print(ans)
    

if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  mod = 10**9 + 7
  n, k = map(int, input().split(' '))
  A = list(range(n+1))
  A_rev = A[::-1]
  cumsum_A = [0]
  cumsum_A_rev = [0]
  for i in range(len(A)):
    cumsum_A.append(A[i]+cumsum_A[i])
    cumsum_A_rev.append(A_rev[i]+cumsum_A_rev[i])
  ans = 0
  
  for i in range(k, n+2):
    tmp_min = cumsum_A[i]
    tmp_max = cumsum_A_rev[i]
    ans += (tmp_max - tmp_min + 1)
  print(ans%mod)
    

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

L,R = map(int,input().split())
A = []

if 2019<=L-R:
  A+=[0]
else:
  for i in range(L,R+1):
    for j in range(L,i):
      A+=[(i*j)%2019]

print(min(A))

### FIXED CODE ###

a = list(map(int,input().split()))
b = []

if a[1]-a[0]>=2019:
  print(0)
else:
  for i in range(a[0],a[1]+1):
    for j in range(a[0],i):
      c = (i*j)%2019
      b.append(c)
  else:
    print(min(b))
### BUGGY CODE ###

n = int(input())
H = list(map(int, input().split()))
ans = 0
for i in range(n):
  if ans >= n-i-1:
    break
  tmp = 0
  for j in range(i, n-1):
    if H[j] >= H[j+1]:
      tmp += 1
    else:
      break
    ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

n = int(input())
H = list(map(int, input().split()))
TMP = []
ans = 0
for i in range(n-1):
  if H[i] >= H[i+1]:
    TMP.append(1)
  else:
    TMP.append(-1)
tmp = 0
for i in range(n-1):
  if TMP[i] == 1:
    tmp += 1
  else:
    ans = max(ans, tmp)
    tmp = 0
ans = max(ans, tmp)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

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

neighbor = {}
dp = [{} for _ in range(n+1)]
for i in range(1,n+1):
    neighbor[i] = []

for i in range(n-1):
    x, y = map(int,input().split())
    dp[x][y] = -1
    dp[y][x] = -1

def calc_dp(x, y):
    if(dp[x][y] != -1):
        return(dp[x][y])

    if(len(dp[y]) == 1):
        dp[x][y] = 2 % m
        return(dp[x][y])

    temp = 1
    for i in dp[y].keys():
        if(i == x):
            continue

        temp = temp * (calc_dp(y,i)) % m

    temp = (temp + 1) % m
    dp[x][y] = temp
    return(temp)

for i in range(1,n+1):
    ans = 1
    for j in dp[i].keys():
        ans = ans * calc_dp(i,j) % m
    print(ans)

### FIXED CODE ###

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

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

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

ini = 1

def calc(a,b):
    p = a * b % mod
    return p

# calc1 の定義
def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    p_num += 1
    dp1[c] = p_num % mod

# calc2 の定義
def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append(calc(a,b))

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1)%mod



# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

# 子→親の値を算出　累積和チックにすることでうに対策。
dp2 = [None] * (n+1)
dp2[root] = ini
for i in order:
    calc2(i)

for i in range(1,n+1):
    ans = calc(dp1[i]-1, dp2[i])
    print(ans)
### BUGGY CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [0]*n

for i in range(1, n):
    s = min(k, i)
    t = []
    for j in range(i-s, i):
        t.append(dp[j] + abs(h[i] - h[j]))
    dp[i] = min(t)

print(dp[-1])


### FIXED CODE ###

import numpy as np

n, k = list(map(int, input().split()))
h = np.array(list(map(int, input().split())))
dp = np.zeros(n)

for i in range(1, n):
    s = min(k, i)
    dp[i] = np.min(dp[i-s:i] + np.abs(h[i] - h[i-s:i]))

#    for j in range(i-s, i):
#        t.append(dp[j] + abs(h[i] - h[j]))

print(int(dp[-1]))
### BUGGY CODE ###

n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**19
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]
for _ in range(q):
    x, y = map(int, input().split())
    x, y = x + k - 2, y + k - 1
    ans = set()
    while x < y:
        if x % 2 == 0:
            ans |= S[x]
            x += 1
        if y % 2 == 0:
            y -= 1
            ans |= S[y]
        x, y = (x - 1) // 2, (y - 1) // 2
    print(len(ans))


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.array = [0] * (n + 1)
        self.size = n

    def sum(self, i):
        s = 0
        tmp = i
        while tmp > 0:
            s += self.array[tmp]
            tmp -= tmp & -tmp
        return s

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main():

    a, b, x = map(int, input().split())
    ans = 0

    for i in range(a, b+1):
        if i % x == 0:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main():

    a, b, x = map(int, input().split())
    ans = 0

    ans = (b // x) - ((a-1) // x)

    print(ans)


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

N, Q = list(map(lambda x: int(x), input().split(' ')))
S = input()

for _ in range(Q):
    l, r = list(map(lambda x: int(x), input().split(' ')))
    l -=1
    r -=1
    ans = 0
    for i in range(l, r):
        # print(S[i:i+2])
        if S[i:i+2] == 'AC':
            ans += 1

    # print(S[l:r+1])
    print(ans)
    # exit()

### FIXED CODE ###

N, Q = list(map(lambda x: int(x), input().split(' ')))
S = input()

#
buf = [0 for _ in range(N)]
prev = 0
for i in range(N-1):
    if S[i:i+2] == 'AC':
        buf[i+1] = prev + 1
    else:
        buf[i+1] = prev

    prev = buf[i+1]

# print(buf)

for _ in range(Q):
    l, r = list(map(lambda x: int(x), input().split(' ')))
    l -=1
    r -=1
    ans = buf[r] - buf[l]
    print(ans)
### BUGGY CODE ###

N = int(input())
H_list = input().split(" ")
max_count = 0
for i in range(0, N):
    S = int(H_list[i])
    count = 0
    for j in range(i + 1, N):
        if S >= int(H_list[j]):
            S = int(H_list[j])
            count += 1
        else:
            break
    if max_count < count:
        max_count = count
    if max_count >= N - i -1:
        break
    if max_count >= N / 2:
        break
print(max_count)



### FIXED CODE ###

N = int(input())
H_LIST = input().split(" ")
H = []

for i in H_LIST:
    H.append(int(i))
   
count = 0
max_count = 0
for i in range(0, N-1):
    if H[i] >= H[i + 1]:
        count += 1
    else:
        count = 0 #メモリの動き
        
    if max_count < count:
        max_count = count


print(max_count)
### BUGGY CODE ###

# 再帰関数使用時は再帰上限を十分にとること
import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
 
# グローバル変数定義
INF = 10 ** 13
N, W = map(int, input().split())
 
# knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
# knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
knapsack = [list(map(int, input().split())) for _ in range(N)]
 
# db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
db = [[INF] * W for _ in range(N)]
 
 
def dfs(n, w):
    """
    品物に対する深さ優先探索による全探索（メモ化再帰）。
 
    Args:
        n (int) : 見てきた品物の数
        w (int) : ここまでの重さの総和
 
    Returns:
        v (int) : 価値の総和の最大値
    """
 
    # 終了条件：現在の個数が全ての品物の個数を越える
    if n >= N:
        return 0
 
    if w + knapsack[n][0] > W:
        # １つ前までの重さ + 今回の品物の重さが重さの最大値を越えていたら今回の品物は選べない
        return dfs(n + 1, w)
    else:
        # 今回の品物を選ぶか選ばないかで全探索
        return max([dfs(n + 1, w), dfs(n + 1, w + knapsack[n][0]) + knapsack[n][1]])
 
 
def main():
    out = dfs(0, 0)
    print(out)
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline


def chmax(a, b):
    """
    2値の大きい値を返す

    Args:
        a   (int)   : 値１
        b   (int)   : 値２
    Return:
        a   (int)   : aまたはbの大きい値
    """
    if a < b:
        a = b
    return a


def main():

    N, W = map(int, readline().split())

    # knopsock[n][0] = w    :   n = 品物の位置 , w = 重さ
    # knopsock[n][1] = v    :   n = 品物の位置 , v = 価値
    knapsack = [list(map(int, readline().split())) for _ in range(N)]

    # db[n][w] = v          :   w = 現在の重さ, n = 見てきた品物の数, v = 現在の価値
    dp = [[0] * (W + 1) for _ in range(N + 1)]

    for n in range(1, N + 1):
        for w in range(W + 1):
            if w - knapsack[n - 1][0] < 0:
                dp[n][w] = dp[n - 1][w]
            else:
                dp[n][w] = chmax(dp[n - 1][w], dp[n - 1]
                                 [w - knapsack[n - 1][0]] + knapsack[n - 1][1])

    print(dp[N][W])


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

import numpy as np

N = int(input())

dicdata = {}
for i in range(N):
	data = input()
	if data in dicdata:
		dicdata[data] += 1
	else:
		dicdata[data] = 1

newdata = [k for k, v in dicdata.items() if v == max(dicdata.values())]

newdata = sorted(newdata)

[print(i) for i in newdata]

### FIXED CODE ###

import collections

N = int(input())
data = [input() for i in range(N)]

dicdata = collections.Counter(data)

m = max(dicdata.values())

newdata = [k for k, v in dicdata.items() if v == m]

newdata.sort()

[print(i) for i in newdata]
### BUGGY CODE ###

N = int(input())
S = list(map(int, input().split()))
b = []
for i in range(N):
  if (i + N) % 2 == 0:
    b.append(S[i])
  else:
    b = [S[i]] + b[:]
for i in range(N - 1):
  print(b[i], end = ' ')
print(b[N - 1])


### FIXED CODE ###

N = int(input())
S = list(map(int, input().split()))
b = [0 for i in range(N)]
if N % 2 == 0:
  for i in range(N):
    if i % 2 == 0:
      b[(N + i) // 2] = S[i]
    else:
      b[(N - i) // 2] = S[i]
else:
  b[N // 2] = S[0]
  for i in range(1, N):
    if i % 2 == 1:
      b[(N + i) // 2] = S[i]
    else:
      b[(N - i) // 2] = S[i]
for i in range(N - 1):
  print(b[i], end = ' ')
print(b[N - 1])
### BUGGY CODE ###

import math

mod = 1000000007

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

n=int(input())

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

memo = a[0]

for i in range(1,n):
    memo = lcm(memo,a[i])

ans = 0

for i in range(n):
    ans += memo//a[i]
    ans %= mod

print(ans)

### FIXED CODE ###

import math
 
mod = 1000000007
 
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
 
n=int(input())
 
a = list(map(int,input().split()))
 
memo = a[0]
 
for i in range(1,n):
    memo = lcm(memo,a[i])
 
ans = 0
 
for i in range(n):
    ans += memo*pow(a[i], mod-2, mod)%mod
    ans %= mod
 
print(ans)
### BUGGY CODE ###

S = input()  #文字
Q = int(input())  #数字
X = [0] * Q
R = 1
for i in range(Q):
    X[i] = list(input().split() ) #文字、複数行複数列
    if X[i][0] == "1":
        R *= - 1
    else:
        if X[i][1] == "1":
            if R == 1:
                S = X[i][2] + S
            else:
                S = S + X[i][2]                
        else:
            if R == 1:
                S = S + X[i][2]                
            else:
                S = X[i][2] + S

print(S[::R])

### FIXED CODE ###

s = input()
q = int(input())
cou = 1
frt = ""
bck = ""
for i in range(q):
    t = list(input().split())
    #logging.debug(t)#
    if t[0] == "1":
        cou *= -1
    else:
        if (t[1] == "1" and cou == 1)or(t[1] == "2" and cou == -1):
            frt = t[2] + frt
        else:
            bck = bck + t[2]
#    logging.debug("s {},cou {}".format(s,cou))

s = frt + s + bck
#logging.debug(s)#
if cou == 1:
    print(''.join(s))
else:
    print(''.join(s[::-1]))
### BUGGY CODE ###

def main():
    import numpy as np
    n = int(input())
    ss = [list(input()) for _ in [0]*n]
    alphabet = "abcdefghijklmnopqrstuvwxyz"
    d = {j: i for i, j in enumerate(alphabet)}
    s = np.array([[d[i] for i in j] for j in ss], dtype=np.int8)

    def check(a):
        for i in range(n):
            for j in range(i):
                if s[i % n][(j+a) % n] != s[j % n][(i+a) % n]:
                    return 0
        return 1
    print(n*sum([check(i) for i in range(n)]))


main()


### FIXED CODE ###

def main():
    n=int(input())
    nn=2*n-1
    s=[input() for _ in [0]*n]
    s=[i+i[:-1] for i in s]+[i+i[:-1] for i in s][:-1]
    ans=[[0]*n for _ in [0]*n]
    for i in range(1,nn):
        m=min(i+1,n)
        for j in range(nn-1):
            for k in range(max(i-j-n,0)+1,min(m,nn-j,i-j+n)):
                ii=i-k
                if s[i][j]!=s[ii][j+k]:
                    l=min(n-k+1,ii,j)
                    width=l-max(-1,ii-n,j-n)
                    ans[ii-l][j-l]=max(ans[ii-l][j-l],width)
    for i in range(1,n):
        for j in range(1,n):
            ans[i][j]=max(ans[i][j],ans[i-1][j-1]-1)
    print(sum([sum([i==0 for i in a]) for a in ans]))
main()
### BUGGY CODE ###

# coding:utf-8

N = int(input())
P = [int(el) for el in input().split(' ')]
ans = 1

for i, p in enumerate(P):
    if i == 0:
        continue
    flag = True
    for j in range(i):
        if p > P[j]:
            flag = False
    if flag:
        ans += 1

print(ans)

### FIXED CODE ###

# coding:utf-8

N = int(input())
P = [int(el) for el in input().split(' ')]
min_val = N+1
ans = 0

for p in P:
    if p < min_val:
        ans += 1
        min_val = p

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

import sys
sys.setrecursionlimit(10 ** 9)


def func(v, color):
    if visited[v] != 2:
        return
    visited[v] = color
    for next_v in range(n):
        if graph[v][next_v]:  # vとnext_vが繋がっている場合
            if graph[v][next_v] & 1:
                func(next_v, 1-color)
            else:
                func(next_v, color)


n = int(input())
side = [[int(x) for x in sys.stdin.readline().split()] for _ in range(n-1)]
graph = [[0] * n for _ in range(n)]
visited = [2] * n  # 2は未訪問 0は白 黒は1

for u, v, w in side:
    graph[u-1][v-1] = graph[v-1][u-1] = w

func(0, 0)

for i in visited:
    print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)


def func(v, c):
    for next_v, w in graph[v]:
        if color[next_v] == -1:
            color[next_v] = (c + w) & 1
            func(next_v, c + w) 

n = int(input())
graph = [[] for _ in range(n)]
color = [-1] * n

for _ in range(n-1):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u-1].append((v-1, w))
    graph[v-1].append((u-1, w))


color[0] = 0
func(0, 0)

for i in color:
    print(i)
### BUGGY CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

s = list(ns())
ls = len(s)
lk = ni()
dp = [[[0]*(lk+1) for _ in range(ls)] for i in range(ls)]
for i in range(ls):
  dp[i][i][0] = 1
for k in range(lk+1):
  for dis in range(1, ls):
    for i in range(ls - dis):
      j = i + dis
      if s[i] == s[j]:
        dp[i][j][k] = dp[i+1][j-1][k] + 2
      elif k:
        dp[i][j][k] = dp[i+1][j-1][k-1] + 2
      dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][k], dp[i][j-1][k])
      
print(max(dp[0][ls-1]))


### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  s = list(ns())
  ls = len(s)
  lk = ni()
  dp = [[[0]*ls for _ in range(ls)] for i in range(2)]
  ans = 0
  for i in range(ls):
    dp[0][i][i] = 1
  for k in range(lk+1):
    v = k & 1
    for dis in range(1, ls):
      for i in range(ls - dis):
        j = i + dis
        dp[v][i][j] = 0
        if s[i] == s[j]:
          dp[v][i][j] = dp[v][i+1][j-1] + 2
        elif k:
          dp[v][i][j] = dp[v^1][i+1][j-1] + 2
        dp[v][i][j] = max(dp[v][i][j], dp[v][i+1][j], dp[v][i][j-1])
    ans = max(ans, dp[v][0][-1])

  print(ans)
  return

solve()
### BUGGY CODE ###

def gcd(p, q) :
	if p % q == 0 :
		return q
	else :
		return gcd(q,p%q)
if __name__ == '__main__':
	ans = 0
	k = int(input())
	for i in range(1,k+1) :
		for j in range(1, k+1) :
			for l in range(1, k+1) :
				ans += gcd(gcd(i,j),l)
	print(ans)


### FIXED CODE ###

def gcd(p, q) :
	if p % q == 0 :
		return q
	else :
		return gcd(q,p%q)
if __name__ == '__main__':
	k = int(input())
	a = []
	ans = 0
	for i in range(1,k+1) :
		for j in range(1,k+1) :
			a.append(gcd(i,j))
	for i in range(1,k+1) :
		for j in a :
			ans += gcd(i,j)
	print(ans)