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

import sys

sys.setrecursionlimit(100000)

class Tree():
    def __init__(self, n, root, connects):
        self.root = root
        self.connects = connects
        self.parents = [0] * n
        self.parents[root] = None
        self.children = [0] * n
        self.children[self.root] = connects[self.root]
        self.make_tree(self.root)

    def make_tree(self, node):
        for child in self.children[node]:
            self.parents[child] = node
            self.children[child] = [c for c in self.connects[child] if c != node]
            if self.children[child] != []:
                self.make_tree(child)


def main():
    n = int(input())
    G = [[] for _ in range(n)]
    ID = [dict() for _ in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
        ID[a][b] = i
        ID[b][a] = i
    t = Tree(n, root = 0, connects = G)
    m = max(len(g) for g in G)
    ans = [0] * (n - 1)
    def bfs(a, pre = set()):
        color = list(set(range(m)) - pre)
        for b in t.children[a]:
            c = color.pop()
            ans[ID[a][b]] = c + 1
            bfs(b, set([c]))
    bfs(0)
    print(m)
    [print(a) for a in ans]
      
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    ID = [dict() for _ in range(n)]
    for i in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        G[a].append(b)
        G[b].append(a)
        ID[a][b] = i
        ID[b][a] = i
    m = max(len(g) for g in G)
    ans = [0] * (n - 1)
    def bfs(a, pre = -1, pre_c = -1):
        color = 1
        for b in G[a]:
            if b == pre: continue
            if color == pre_c: color += 1
            ans[ID[a][b]] = color
            bfs(b, a, color)
            color += 1

    bfs(0)
    print(m)
    [print(a) for a in ans]
      
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s=input()
q=int(input())
flag=0
t=['' for _ in range(2)]
cnt=0
for _ in range(q):
  a=list(input().split())
  if a[0]=='1':
    flag=1-flag
    cnt+=1
  else:
    if a[1]=='1':t[flag]+=a[2]
    else:t[1-flag]+=a[2]
if cnt%2:ans=t[1][::-1]+s[::-1]+t[0]
else:ans=t[0][::-1]+s+t[1]
print(ans)

### FIXED CODE ###

s=input()
q=int(input())
flag=0
t=['' for _ in range(2)]
cnt=0
for _ in range(q):
  a=list(input().split())
  if a[0]=='1':
    flag=1-flag
    cnt+=1
  else:
    if a[1]=='1':t[flag]+=a[2]
    else:t[1-flag]+=a[2]
ans=t[0][::-1]+s+t[1]
if cnt%2:ans=ans[::-1]
print(ans)
### BUGGY CODE ###

N, Y = map(int, input().strip().split())

# s :  1000円札の枚数
# g :  5000円札の枚数
# i : 10000円札の枚数

ans = '-1 -1 -1'

for s in range(N + 1):
    for g in range(N + 1 - s):
        for i in range(N + 1 - s - g):
            money = 1000 * s + 5000 * g + 10000 * i
            if money == Y:
                ans = str(i) + " " + str(g) + " " + str(s)
                

print(ans)

### FIXED CODE ###

N, Y = map(int, input().strip().split())

# s :  1000円札の枚数
# g :  5000円札の枚数
# i : 10000円札の枚数

ans = '-1 -1 -1'
flag = 0

for s in range(N + 1):
    if flag == 1:
        break

    for g in range(N + 1 - s):
        i = N - s - g
        money = 1000 * s + 5000 * g + 10000 * i
        if money == Y:
            ans = str(i) + " " + str(g) + " " + str(s)
            flag = 1
            break


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

from math import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
gc=reduce(gcd,a)
for i in range(n):
  a[i]//=gc
ans=reduce(gcd,a[1:])
ans=max(ans,reduce(gcd,a[:n-1]))
for i in range(1,n-1):
  ans=max(gcd(reduce(gcd,a[:i]),reduce(gcd,a[i+1:])),ans)
print(ans*gc)

### FIXED CODE ###

from math import*
n=int(input())
a=list(map(int,input().split()))
b=[a[0]]
c=[a[-1]]
for i in range(1,n):
  b+=[gcd(b[-1],a[i])]
  c+=[gcd(c[-1],a[-i-1])]
ans=0
c=c[::-1]
for i in range(n):
  if i==0:ans=max(ans,c[i+1])
  elif i==n-1:ans=max(ans,b[i-1])
  else:
    ans=max(ans,gcd(c[i+1],b[i-1]))
print(ans)
### BUGGY CODE ###

n = int(input())
p = [int(input()) for i in range(n)]
asc = 0
desc = 0
for t in range(1, n+1):
    target = t
    tmp = 0
    for i in p:
        if i == target:
            tmp += 1
            target += 1
    asc = max(asc, tmp)
for t in range(n, 0, -1):
    target = t
    tmp = 0
    for i in reversed(p):
        if i == target:
            tmp += 1
            target -= 1
    desc = max(desc, tmp)

ans = n - max(asc, desc)
print(ans)

### FIXED CODE ###

n = int(input())
p = [int(input()) for i in range(n)]
tl = 1
n2i = [-1 for i in range(n)]
for i in range(n):
    n2i[p[i]-1] = i
tmp = 1
for i in range(n-1):
    if n2i[i] < n2i[i+1]:
        tmp += 1
    else:
        tmp = 1
    tl = max(tl, tmp)

ans = n - tl
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

total = sum(A)

for i in range(Q):
    if(B[i] in A):
        count = A.count(B[i])

        d = C[i] - B[i]
        total += count * d
        print(total)

        A = [C[i] if x == B[i] else x for x in A]
    else:
        print(total)


### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

max_num = max(max(A), max(B), max(C))

NUM = [0] * (max_num + 1)

num_list = []

for a in A:
    NUM[a] += 1

total = sum(A)

for i in range(Q):

    total += (C[i] - B[i]) * NUM[B[i]]
    NUM[B[i]], NUM[C[i]] = 0, NUM[B[i]] + NUM[C[i]]

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

from bisect import bisect_left
from collections import deque
N,M = map(int,input().split())
PY = []
S =[[] for _ in range(N)]

for i in range(M):
    PY.append(list(map(int,input().split())))
    S[PY[i][0]-1].insert(bisect_left(S[PY[i][0]-1],PY[i][1]),PY[i][1])

for i in range(M):
    x = bisect_left(S[PY[i][0]-1],PY[i][1])+1
    print(str(PY[i][0]).zfill(6)+str(x).zfill(6))







### FIXED CODE ###

from bisect import bisect_left
from collections import deque
N,M = map(int,input().split())
PY = []
S =[[] for _ in range(N)]

for i in range(M):
    PY.append(list(map(int,input().split())))
    S[PY[i][0]-1].append(PY[i][1])

for i in range(N):
	S[i].sort()

for i in range(M):
    x = bisect_left(S[PY[i][0]-1],PY[i][1])+1
    print(str(PY[i][0]).zfill(6)+str(x).zfill(6))
### BUGGY CODE ###

S = input()
T = [0 * x for x in range(len(S))]
Rcount = 0
Lcount = 0

for i in range(len(S)):
  if S[i] == 'R':
    j = i
    c = 0
    while (True):
      if S[j] == 'R':
        c += 1
        j += 1
      else:
        if c % 2 == 0:
          T[j] += 1
          #print (i, S[i], c, j)
        else:
          T[j-1] += 1
          #print (i, S[i], c, j-1)
        break
  else:
    j = i
    c = 0
    while (True):
      if S[j] == 'L':
        c += 1
        j -= 1
      else:
        if c % 2 == 0:
          T[j] += 1
          #print (i, S[i], c, j)
        else:
          T[j+1] += 1
          #print (i, S[i], c, j+1)
        break
print(T[0], end ="")
for i in range(len(S)-1):
  print (" " + str(T[i+1]), end ="")

### FIXED CODE ###

S = input()
T = [0 * x for x in range(len(S))]
Rcount = 0
Lcount = 0

for i in range(len(S)):
  if S[i] == 'R':
    j = S[i:].find('L')
    if j % 2 == 0:
      T[i+j] += 1
    else:
      T[i+j-1] += 1
  else:
    j = S[:i].rfind('R')
    if (i-j) % 2 == 0:
      T[j] += 1
    else:
      T[j+1] += 1

print(T[0], end ="")
for i in range(len(S)-1):
  print (" " + str(T[i+1]), end ="")
### BUGGY CODE ###

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

### 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 ###

n, m = map(int, input().split())
des = []
first = []
second = []
a = 1
for i in range(0, m):
	des.append(list(map(int, input().split())))
###ここまで入力
###以下出力
for i in des:
	if i[0] == 1:
		first.append(i[1])
	if i[1] == n:
		second.append(i[0])
###以上1から行ける場所をfirstに格納 終点につながるとこをsecondに格納

for i in first:
	if i in second:
		print('POSSIBLE')
		a = 0
		break

if a:
	print('IMPOSSIBLE')





### FIXED CODE ###

n, m = map(int, input().split())
des= [0]*(n+1)
a = 1
for i in range(0, m):
	b = (list(map(int, input().split())))
	if b[0] == 1:
		des[b[1]] += 1
		if des[b[1]] == 2:
			print('POSSIBLE')
			a = 0
			break
	if b[1] == n:
		des[b[0]] += 1
		if des[b[0]] == 2:
			print('POSSIBLE')
			a = 0
			break
		
if a:
	print('IMPOSSIBLE')
### BUGGY CODE ###

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

c = [0]*N
ans = 0
for i in range(N):
  c[i] = A.count(i+1)
  if c[i]>1:
    ans+=c[i]*(c[i]-1)//2

for i in range(N):
  print(ans-(c[A[i]-1]-1)) if c[A[i]-1]>1 else print(ans)

### FIXED CODE ###

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

c = collections.Counter(A)
ans = 0
for i in c:
  ans+=c[i]*(c[i]-1)//2

for i in range(N):
  print(ans-(c[A[i]]-1))
### BUGGY CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])
rM = 0
for i in range(N):
  for lr in LR:
    if lr[0] <= i and i <= lr[1]:
      S.append(i)
  rM = max(rM, lr[1])
for i in range(1,N):
  if i in S:
    dp[i] = 1
  for l,r in LR:
    l,r = i - r,i - l
    if r < 1:
      continue
    l = max(0,l)
    dp[i] += dps[r] - dps [l-1]
    dp[i] %= mod
    dps[i] += dps[r] - dps[l]
    
  dps[i] = dps[i-1] + dp[i]
print(dp[-2])

### FIXED CODE ###

N,K = [int(i) for i in input().split()]
mod = 998244353
LR = []
S = []
dp = [0]*(N+1)
dps = [0]*(N+1)
dps[1] = 1
dp[1] = 1
for i in range(K):
  LR.append([int(i) for i in input().split()])

for i in range(1,N+1):
  for l,r in LR:
    l,r = i - r,i - l
    #print(l,r)
    if r < 1:
      continue
    l = max(1,l)
    dp[i] += dps[r] - dps[l-1]
    dp[i] %= mod
    #print(dp[i])
    
  dps[i] = dps[i-1] + dp[i]
  #print(dp, dps)
print(dp[-1])
### BUGGY CODE ###

#problem D
input_d41 = int(input())
input_d42 = input()

N = int(input_d41)
S = input_d42

R = S.count('R')
G = S.count('G')
B = S.count('B')

ans = 0
answ = 0

for i in range(0,N):
    for j in range(i+1,N):
        if S[i] != S[j] and 2*j-i < N:
            if S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                answ += 1
            
ans = R*G*B - answ

print(ans)

### FIXED CODE ###

#problem D
input_d41 = int(input())
input_d42 = input()

N = int(input_d41)
S = input_d42

R = S.count('R')
G = S.count('G')
B = N - (R + G)

ans = R*G*B
answ = 0

for i in range(0,N):
    for j in range(i+1,(N+i)//2 +1):
        if S[i] != S[j]:
            if 2*j-i < N and S[j] != S[2*j-i] and S[2*j-i] != S[i]:
                ans -= 1
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop(0)
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

answer = ' '.join(map(str,Counter[1:]))
print(answer)

### FIXED CODE ###

n, q = map(int, input().split())
Tree = [[] for _ in range(n+1)]
Counter = [0 for _ in range(n+1)]
AB = (tuple(map(int, input().split())) for _ in range(n-1))
PX = (tuple(map(int, input().split())) for _ in range(q))

for a,b in AB:
  Tree[a].append(b)
  Tree[b].append(a)
  
for p,x in PX:
  Counter[p] += x

P = [-1]*(n+1)

nodes = [1]
while nodes:
  parent = nodes.pop()
  for node_i in Tree[parent]:
    if P[parent]==node_i:
      continue
    P[node_i] = parent
    nodes.append(node_i)
    Counter[node_i] += Counter[parent]

print(*Counter[1:])
### BUGGY CODE ###

import numpy as np

N = int(input())
p0_list = np.array([float(item) for item in input().split()])
p1_list = 1 - p0_list

dp = np.zeros((N+1, N+1), dtype='float')
dp[0, 0] = 1


for i in range(N):
    dp[i+1, 0] = dp[i, 0] * p1_list[i]
    for j in range(i+1):
        dp[i+1, j+1] = dp[i, j] * p0_list[i] + dp[i, j+1] * p1_list[i]

# print(dp)
print(sum(dp[N, N//2 + 1:]))

    

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

N = int(input())
p0_list = np.array([float(item) for item in input().split()])
p1_list = 1 - p0_list

dp = np.zeros((N+1, N+1), dtype='float')
dp[0, 0] = 1

for i in range(N):
    dp[i+1][:-1] += dp[i][:-1] * p1_list[i]
    dp[i+1][1:]  += dp[i][:-1] * p0_list[i]

print(np.sum(dp[N, (N+1)//2:]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


h, w = map(int, input().split())

GRID = []
for _ in range(h):
    s = input().strip()
    R = [0 if c == "#" else 1 for c in s]
    GRID.append(R)

LEFT = [R.copy() for R in GRID]
for i in range(h):
    for j in range(1, w):
        if LEFT[i][j] == 0:
            continue
        LEFT[i][j] += LEFT[i][j - 1]

RIGHT = [R.copy() for R in GRID]
for i in range(h):
    for j in range(w - 2, -1, -1):
        if RIGHT[i][j] == 0:
            continue
        RIGHT[i][j] += RIGHT[i][j + 1]

TOP = [R.copy() for R in GRID]
for j in range(w):
    for i in range(1, h):
        if TOP[i][j] == 0:
            continue
        TOP[i][j] += TOP[i - 1][j]

BOTTOM = [R.copy() for R in GRID]
for j in range(w):
    for i in range(h - 2, -1, -1):
        if BOTTOM[i][j] == 0:
            continue
        BOTTOM[i][j] += BOTTOM[i + 1][j]

LIGHTED = [[0] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        LIGHTED[i][j] = LEFT[i][j] + RIGHT[i][j] + TOP[i][j] + BOTTOM[i][j] - 3

answer = 0
for i in range(h):
    for j in range(w):
        if LIGHTED[i][j] > answer:
            answer = LIGHTED[i][j]

print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np


h, w = map(int, input().split())

GRID = []
for _ in range(h):
    S = [0] + [0 if c == "#" else 1 for c in input().strip()] + [0]
    GRID.append(S)
GRID.insert(0, [0] * (w + 2))
GRID.append([0] * (w + 2))
grid = np.array(GRID)

top = np.zeros((h + 2, w + 2), dtype = np.int)
bottom = np.zeros((h + 2, w + 2), dtype = np.int)
left = np.zeros((h + 2, w + 2), dtype = np.int)
right = np.zeros((h + 2, w + 2), dtype = np.int)

for i in range(1, h + 1):
    top[i] = (top[i - 1] + 1) * grid[i]
for i in range(h, 0, -1):
    bottom[i] = (bottom[i + 1] + 1) * grid[i]
for j in range(1, w + 1):
    left[:, j] = (left[:, j - 1] + 1) * grid[:, j]
for j in range(w, 0, -1):
    right[:, j] = (right[:, j + 1] + 1) * grid[:, j]

column = (top + bottom - 1) * grid
row = (left + right - 1) * grid
lighted = (column + row - 1) * grid

ans = lighted.max()
print(ans)
### BUGGY CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
S = sum(alist)
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = [{} for i in range(N+1)]
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = [{} for i in range(N+1)]

def ddp(cur_N, R): #(retA: R>=S/2となる数, retB: R=G=S/2,B=0の数)を返す
    if R in dptableA[cur_N]: #DPテーブルにある
        return dptableA[cur_N][R], dptableB[cur_N][R]
    if cur_N == N: #末端
        retA = 1 if R >= Sharf else 0
        retB = 1 if R == Sharf else 0
        return retA, retB
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        retA = pow(3, N-cur_N, MOD)
        retB = 1 if R == Sharf else 0 #特にR=S/2の時はR=G=S/2にできる
        return retA, retB
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retA_R, retB_R = ddp(cur_N+1, R+ai) #Rに振り分けた場合
    retA_GB, retB_GB = ddp(cur_N+1,R) #Rに入れなかった場合
    retA_GB = retA_GB * 2 %MOD #GBで2通りあるので2倍
    retA = (retA_R + retA_GB) % MOD
    retB = (retB_R + retB_GB) % MOD
    dptableA[cur_N][R] = retA
    dptableB[cur_N][R] = retB
    return retA, retB

retA, retB = ddp(0,0)
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

### FIXED CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
import numpy as np
### 三角形が成立しない場合を数える
alist.sort(reverse=False) #大きい方からチェックするとS/2に早く到達しやすい
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
dptableA[N, int(np.ceil(Sharf)):] = 1
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
if S %2 == 0:
    dptableB[N, int(Sharf)] = 1 

#dpの計算をまとめて行う
for i in range(N, 0, -1): #後ろから見ていく
    n = i - 1
    an = alist[n]
    asn = asum[n]
    dptableA[n, 0:asn+1] = (2*dptableA[n+1, 0:asn+1] + dptableA[n+1, an:an+asn+1])%MOD
    #dptableA[n] = [(2*dptableA[n+1][k]+dptableA[n+1][k+alist[n]]) % MOD for k in range(asum[n]+1)]
    dptableB[n, 0:asn+1] = (dptableB[n+1, 0:asn+1] + dptableB[n+1, an:an+asn+1])%MOD
    #dptableB[n] = [(dptableB[n+1][k]+dptableB[n+1][k+alist[n]]) %MOD for k in range(asum[n]+1)]
retA, retB = dptableA[0,0], dptableB[0,0]
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)
### BUGGY CODE ###

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

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

mj = []

for i in range(m):
    mj.append(list(map(int,input().split())))
    
tower = []

for i in range(n):
    #自分からのびている道から先にある展望台を探索し、自分iと比較
    cnt = 0
    h_high = 0
    for j in range(m):
        if i+1 in mj[j]:
            cnt += 1
            if i == mj[j][0]-1:
                if h[i] > h[mj[j][1]-1]:
                    h_high += 1
            else:
                if h[i] > h[mj[j][0]-1]:
                    h_high += 1
    if cnt == h_high:
        tower.append(i)
        
print(len(tower))

### FIXED CODE ###

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

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

mj = []

for i in range(m):
    mj.append(list(map(int,input().split())))

cnt_w = [0 for _ in range(n)]
cnt = [0 for _ in range(n)]

for i in range(m):
    cnt[mj[i][0]-1] += 1
    cnt[mj[i][1]-1] += 1
    if h[mj[i][0]-1] > h[mj[i][1]-1]:
        cnt_w[mj[i][0]-1] += 1
    elif h[mj[i][0]-1] < h[mj[i][1]-1]:
        cnt_w[mj[i][1]-1] += 1

tower = 0
for i in range(n):
    if cnt[i] == cnt_w[i]:
        tower += 1
print(tower)
### BUGGY CODE ###

import functools
from fractions import gcd
n = int(input())
@functools.lru_cache(None)
def main(n):
  g=0
  for i in range (1, n+1):
    for j in range (1, n+1):
      for k in range (1, n+1):
        g  += gcd(gcd(i,j),k)
  return (g)
print(main(n))

### FIXED CODE ###

from math import gcd
N = int(input())
ans = 0
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 ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    ans = 0

    for i in range(N):
        flg = True
        for j in range(i+1):
            if P[i] > P[j]:
                flg = False
        if flg == True:
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    P = [int(x) for x in input().split()]
    ans = 0
    minP = P[0]

    for i in range(N):
        minP = min(minP, P[i])
        if P[i] <= minP:
            ans += 1
    
    print(ans)
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections

def main():
    n = int(input())
    c = []
    count = 0
    lists =[]

    for num in range(n):
        c.append(''.join(sorted(input())))

    for i in c:
        if i in lists:
            count = count + lists.count(i)
            lists.append(i)
        else:
            lists.append(i)

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)
### BUGGY CODE ###

if __name__ == '__main__':
    l = list(map(int, input().split()))
    X = int(l[0])
    K = int(l[1])
    D = int(l[2])
    
    if D*K <= abs(X):
        minVal=abs(X) - D*K
    else:
        n=0
        while abs(X) - D*n > 0:
            n=n+1
        
        if (K-n)%2==0:
            minVal = abs(abs(X) - D*n)
        else:
            minVal = abs(abs(X) - D*(n-1))
        
    print(minVal)

### FIXED CODE ###

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

import math

if __name__ == '__main__':
    l = list(map(int, input().split()))
    X = int(l[0])
    K = int(l[1])
    D = int(l[2])
    
    if D*K <= abs(X):
        minVal=abs(X) - D*K
    else:
        n=math.floor(abs(X)/D)+1
        # while abs(X) - D*n > 0:
        #    n=n+1
        
        if (K-n)%2==0:
            minVal = abs(abs(X) - D*n)
        else:
            minVal = abs(abs(X) - D*(n-1))
        
    print(minVal)
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [input().split() for i in range(Q)]

for i in range(Q):
    if Query[i][0] == '1':
        S = S[::-1]
    else:
        F = Query[i][1]
        C = Query[i][2]
        if F == '1':
            S = C + S
        else:
            S = S + C

print(S)


### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
Query = [input().split() for i in range(Q)]
order = 1

for i in range(Q):
    if Query[i][0] == '1':
        order *= -1
    else:
        F = Query[i][1]
        C = Query[i][2]

        if F == '1':
            if order == 1:
                S.appendleft(C)
            else:
                S.append(C)
        else:
            if order == 1:
                S.append(C)
            else:
                S.appendleft(C)

S = ''.join(list(S))

print(S[::order])
### BUGGY CODE ###

def main():
    n, w_max = map(int, input().split())
    dp = [[0] * (w_max + 1) for _ in range(n + 1)]
    items = [tuple(map(int, input().split())) for _ in range(n)]
    for i1 in range(1, n + 1):
        w, v = items[i1 - 1][0], items[i1 - 1][1]
        for col in range(1, w_max + 1):
            if w <= col:
                dp[i1][col] = max(dp[i1 - 1][col], dp[i1 - 1][col - w] + v)
            else:
                dp[i1][col] = dp[i1 - 1][col]

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


if __name__ == '__main__':
    main()


### FIXED CODE ###

n, w = map(int, input().split())
things = []
things.append([0,0])
things += [list(map(int, input().split())) for _ in range(n)]

dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]

def do_dp():
  for i,thing in enumerate(things):
    dp_1 = dp[i-1]
    for j in range(1, w + 1):      
      dp[i][j] = dp_1[j-thing[0]] + thing[1]  if (j - thing[0]) >= 0 else dp_1[j]
      dp[i][j] = max(dp[i][j], dp_1[j])

do_dp()
print(dp[n][w])
### BUGGY CODE ###

n, k, q = (int(_) for _ in input().split())
a = [int(input()) for _ in range(q)]

for i in range(1, n+1):
    print('Yes' if k - q + a.count(i) > 0 else 'No')


### FIXED CODE ###

n, k, q = (int(_) for _ in input().split())

a = [k-q] * (n+1)
for i in range(q):
    a[int(input())] += 1

for i in range(1, n+1):
    print('Yes' if a[i] > 0 else 'No')