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

from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1


def swap(board, move_from, move_to):
    mf, mt = 4 * move_from, 4 * move_to
    return board + ((1 << mf) - (1 << mt)) * (15 - ((board >> mf) & 15))


def estimate(board):
    return sum(manhattan[i][(board >> (4 * i)) & 15] for i in range(15))


queue = [(0, 0, board_init, blank_init)]
visited = set()

while True:
    _, cost, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(cost)
        break
    visited.add(board)
    cost += 1
    for new_blank in movables[blank]:
        new_board = swap(board, new_blank, blank)
        if new_board in visited:
            continue
        new_estimation = cost + estimate(new_board)
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, cost, new_board, new_blank))

### FIXED CODE ###

from heapq import heappop, heappush

manhattan = [[abs((i % 4) - (j % 4)) + abs((i // 4) - (j // 4)) for j in range(16)] for i in range(16)]
movables = [{1, 4}, {0, 2, 5}, {1, 3, 6}, {2, 7}, {0, 5, 8}, {1, 4, 6, 9}, {2, 5, 7, 10}, {3, 6, 11},
            {4, 9, 12}, {5, 8, 10, 13}, {6, 9, 11, 14}, {7, 10, 15}, {8, 13}, {9, 12, 14}, {10, 13, 15}, {11, 14}]
swap_mul = [[(1 << mf) - (1 << mt) for mt in range(0, 64, 4)] for mf in range(0, 64, 4)]
destination = 0xfedcba9876543210

i = 0
board_init = 0
blank_init = 0
for _ in range(4):
    for n in map(int, input().split()):
        if n:
            n -= 1
        else:
            n = 15
            blank_init = i
        board_init += n * 16 ** i
        i += 1

estimation_init = sum(manhattan[i][((board_init >> (4 * i)) & 15)] for i in range(16) if i != blank_init)

queue = [(estimation_init, board_init, blank_init)]
visited = set()

while True:
    estimation, board, blank = heappop(queue)
    if board in visited:
        continue
    elif board == destination:
        print(estimation)
        break
    visited.add(board)
    for new_blank in movables[blank]:
        num = (board >> (4 * new_blank)) & 15
        new_board = board + swap_mul[new_blank][blank] * (15 - num)
        if new_board in visited:
            continue
        new_estimation = estimation + 1 - manhattan[new_blank][num] + manhattan[blank][num]
        if new_estimation > 45:
            continue
        heappush(queue, (new_estimation, new_board, new_blank))
### BUGGY CODE ###

from operator import mul
from functools import reduce


def combinations_count(n, r):
    if n < r:
        return 0
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom


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

l1 = []
l2 = []
lll = []
dl = []

for i in l:
    t = l.count(i)
    temp = combinations_count(t, 2)
    if i not in dl:
        dl.append(i)
        lll.append(temp)
    l1.append(temp)
    l2.append(combinations_count(t-1, 2))

total = sum(lll)

for i in range(len(l)):
    print(total-l1[i]+l2[i])


### FIXED CODE ###

import collections

def combinations_count(n, r):
    return n * (n-1) // r


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

l1 = []
l2 = []
c = collections.Counter(l)

total = sum([combinations_count(i, 2) for i in c.values()])

for a in l:
    print(total-combinations_count(c[a], 2)+combinations_count(c[a]-1, 2))
### BUGGY CODE ###

import math
n, k = map(int,input().split())
a = list(map(int, input().split()))

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = [i for i in range(2,gcdmax+1)]
li2 = [asum//i for i in range(gcdmax,0,-1)]
li = li + li2

ans = 1

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

print(ans)

### FIXED CODE ###

import math
n, k = map(int,input().split())
a = list(map(int, input().split()))

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = []
for i in range(2,gcdmax+1):
    if asum%i==0:
        li.append(i)
for i in range(gcdmax,0,-1):
    if asum%i==0:
        li.append(asum//i)


ans = 1
# print(li)

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
#     print(i,b)
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
#         print(l,r)
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

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

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                s = query[i][2] + s
            else:
                s = s + query[i][2]
        else:
            if query[i][1] == '2':
                s = query[i][2] + s
            else:
                s = s + query[i][2]
if rev == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

import sys
import numpy as np

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = s[0][0]
A = np.array(s[1])
Q = s[2][0]
BC = np.array(s[3:])
B = BC[:, 0]
C = BC[:, 1]

A_sum = np.sum(A)

D = np.array([np.count_nonzero(A == i) for i in range(100001)])
for i in range(Q):
    b = B[i]
    c = C[i]
    A_sum += D[b] * (c - b)
    print(A_sum)
    D[c] += D[b]
    D[b] = 0


### FIXED CODE ###

import sys
import numpy as np
from collections import Counter

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = s[0][0]
A = np.array(s[1])
Q = s[2][0]
BC = np.array(s[3:])
B = BC[:, 0]
C = BC[:, 1]

A_sum = np.sum(A)

D = Counter(A)

for i in range(Q):
    b = B[i]
    c = C[i]
    A_sum += D[b] * (c - b)
    print(A_sum)
    D[c] += D[b]
    D[b] = 0
### BUGGY CODE ###

from collections import deque

N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]
 
# フレンドの隣接リスト
for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)
 
# ブロックの隣接リスト
for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)
 
 
# 交友関係グループ（辞書型）
D = {}
# グループの親
parent = [-1] * N
# 訪問管理
visited = [False] * N
stack = deque()
 
for root in range(N):
    if visited[root]:
        continue
 
    D[root] = set([root])
    # 訪問先のスタック
    stack.append(root)
    # 訪問先が無くなるまで
    while len(stack)>0:
        # 訪問者をポップアップ
        n = stack.pop()
        if visited[n]:
            continue
        # 訪問者を訪問済み
        visited[n] = True
        # 訪問者のグループの親を設定
        parent[n] = root
 
        # root のフレンドをグループと訪問先に追加
        D[root]=D[root] | set(F[n])
        stack.extend(F[n])
 
ans = [0] * N
for iam in range(N):
    # 自分の交友関係グループを設定
    group = D[parent[iam]]
    # グループからフレンドと自分を除く
    tmp_ans = len(group) - len(F[iam]) - 1
    # グループからブロックを除く
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans
 
print(*ans, sep=' ')

### FIXED CODE ###

from collections import deque

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

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

for i in range(k):
    c,d =(map(int,input().split()))
    c,d = c-1,d-1
    cannotgo[c].append(d)
    cannotgo[d].append(c)
# print(a)
# cango = [[]for i in range(n)]
# for i in a:
#     cango[i[0]-1].append(i[1]-1)
#     cango[i[1]-1].append(i[0]-1)
# print(cango)

# cannotgo=[[]for i in range(n)]
# for i in c:
#     cannotgo[i[0]-1].append(i[1]-1)
#     cannotgo[i[1]-1].append(i[0]-1)
# # print(cannotgo)
alre = [False]*n
parent = [-1]*n
gro = {}
y = deque()
# print(gro)
for i in range(n):
    # if alre[i]==True:
    #     continue
    # gro[i]=set([i])
    y.append(i)
    leader = i
    cnt = 0 
    while len(y)>0:
        x = y.popleft()
        if parent[x]!=-1:
            continue
            # print(to)
        parent[x]=leader
        y.extend(cango[x])
        cnt +=1
    if cnt!=0:
        gro[leader]=cnt
# print(gro)
# print(parent)
ans = [0]*n
# print(ans)
for iam in range(n):
    # group = gro[parent[iam]]
    tmp_ans = gro[parent[iam]]
    tmp_ans -=1
    tmp_ans -= len(cango[iam])
    for block in cannotgo[iam]:
        if parent[block]==parent[iam] :
            tmp_ans -=1
    ans[iam]=tmp_ans
print(*ans, sep=' ')
### BUGGY CODE ###

#import time 

#t1 = time.time()
N, K = map(int, input().split())
#P_list = [i for i in map(int, input().split())]

def func(a):
	a_list = [i/a for i in range(1, a+1)]
	return sum(a_list)

ALL_dice = [i for i in range(1, 1001)]
ALL_exp = list(map(func, ALL_dice))



#P_exp = list(map(func, P_list))

P_exp = [ALL_exp[i-1] for i in map(int, input().split())]

A_list = []
sum_K = 0
for i in range(N-K+1):
	for j in range(K):
		sum_K += P_exp[i+j]

	A_list.append(sum_K)
	sum_K = 0

print(max(A_list))
#print(A_list)
#t2 = time.time()
#print(t2-t1)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
P_exp = np.array([0] + [(1+i)/2 for i in map(int, input().split())])
E_sum = np.cumsum(P_exp)

print((E_sum[K:]-E_sum[:-K]).max())
### BUGGY CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
M = 1
for i in range (0,K):
    M *= A[i]
while True:
    A.pop(0)
    if len(A) == K - 1:
        break
    P = 1
    for i in range (0,K):
        P *= A[i]
        if P > M:
            break
    print('Yes' if P > M else 'No')
    M = P
        


### FIXED CODE ###

N,K = map(int, input().split())
A = list(map(int, input().split()))
for i in range (K,N):
    print('Yes' if A[i] > A[i-K] else 'No')
### BUGGY CODE ###

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

import networkx as nx

edges = []
for _ in range(M):
    i,j=map(int, input().split())
    i-=1
    j-=1
    edges.append([i,j])
G = nx.Graph()
G.add_nodes_from(range(N))
G.add_edges_from(edges)
sg = nx.connected_components(G)
connected = sorted(sg)

max_len = 0
for nodes in connected:
    len_ = len(nodes)
    if len_>max_len:
        max_len=len_
print(max_len)


### FIXED CODE ###

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

class UnionFind():
    def __init__(self, n):
        self.n = n # ノード数
        self.parents = [-1]*n # 各ノードごとのparent

    def find(self, x):
        # 自身が根であれば
        if self.parents[x]<0:
            return x
        # そうでなければ、再帰的に繰り返し、自身の根を探索
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        # それぞれの根
        x = self.find(x)
        y = self.find(y)

        # 根が同一であれば
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x]+=self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

uf = UnionFind(N)
for _ in range(M):
    i, j = map(int, input().split())
    i-=1
    j-=1
    uf.union(i,j)

max_size = 0
for i in range(N):
    if uf.parents[i]<0:
        size = uf.size(i)
        if max_size<size:
            max_size = size
print(max_size)
### BUGGY CODE ###

n=int(input())
suji=[]
for i in range (n):
	suji=suji+list(map(int,input().split()))
tlist=[]
alist=[]
for i in range(2*n):
	if i%2==0:
		tlist.append(suji[i])
	else:
		alist.append(suji[i])

for i in range(n-1):
	k=1
	while tlist[i]>tlist[i+1]*k or alist[i]>alist[i+1]*k:
		k+=1
	tlist[i+1]=tlist[i+1]*k
	alist[i+1]=alist[i+1]*k

print(int(tlist[n-1]+alist[n-1]))

### FIXED CODE ###

n=int(input())
suji=[]
for i in range (n):
	suji=suji+list(map(int,input().split()))
tlist=[]
alist=[]
for i in range(2*n):
	if i%2==0:
		tlist.append(suji[i])
	else:
		alist.append(suji[i])

for i in range(n-1):
	aaa=alist[i]//alist[i+1]
	ttt=tlist[i]//tlist[i+1]
	if alist[i]%alist[i+1]!=0:
		aaa+=1
	if tlist[i]%tlist[i+1]!=0:
		ttt+=1
	k=max(aaa,ttt)
	tlist[i+1]=tlist[i+1]*k
	alist[i+1]=alist[i+1]*k

print(int(tlist[n-1]+alist[n-1]))
### BUGGY CODE ###

import sys
#dp = { 0:0, 1:1, 2:1 }
N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def f(num, popcnt):
    #print(dp)

    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    
    if popcnt == -1:
        b = bin(num)
        popcnt = b.count('1')
    
    if num % popcnt == 0:
        return 1
    else:
        return f(num % popcnt, -1) + 1

nX = int(X, 2)
pcnt = X.count('1')

for i in range(0, N):
    if X[i] == '0':
        print(f(nX + 2**(N-i-1), pcnt+1))
    else:
        print(f(nX - 2**(N-i-1), pcnt-1))


### FIXED CODE ###

import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

#nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print(f(k) + 1)
    else:
        if MOD2 == 0:
            print(0)
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print(f(k) + 1)
### BUGGY CODE ###

n=input()
are=list(map(int,input().split()))
for i in range(len(are)):
    kotae=0
    sin=[0]
    for j in range(len(are)):
        if j != i:
            sin.append(are[j])
    sin.append(0)
    for k in range(len(sin)-1):
        kotae += abs(sin[k+1]-sin[k])
    print(kotae)


### FIXED CODE ###

n = int(input())
a = [0]
a += list(map(int, input().split()))
a.append(0)
ans = 0
for i in range(1, n + 1):
    ans += abs(a[i] - a[i + 1])
for i in range(n):
    ans -= abs(a[i+1]-a[i+2])
    print(ans+abs(a[i] - a[i + 2]))
    ans += abs(a[i] - a[i + 1])
### BUGGY CODE ###

from itertools import chain
chain_from_iterable = chain.from_iterable
from collections import Counter

def divisors(n):
    divisors = {1, n}
    for i in range(2, int(n**0.5)+1):
        q, r = divmod(n, i)
        if not r:
            divisors.add(i)
            divisors.add(q)
    return divisors

n = int(input())
A = map(int, input().split())
B = (divisors(a) for a in A)
c = Counter(chain_from_iterable(B))
print(max(k for k, v in c.items() if v >= n-1))

### FIXED CODE ###

from fractions import gcd

n = int(input())
*A, = map(int, input().split())
B = A[::-1]
L, R = [0]*(n+1), [0]*(n+1)
for i in range(n):
    L[i+1] = gcd(L[i], A[i])
    R[i+1] = gcd(R[i], B[i])
L, R = L[:n], R[:n][::-1]
print(max(gcd(l, r) for l, r in zip(L, R)))
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] == S[j]:
            continue
        elif set([S[i], S[j]]) == {"R", "G"}:
            ans += S[j+1:].count("B")
            if 2*j - i < N and S[2*j - i] == "B":
                ans -= 1
        elif set([S[i], S[j]]) == {"B", "G"}:
            ans += S[j+1:].count("R")
            if 2*j - i < N and S[2*j - i] == "R":
                ans -= 1
        elif set([S[i], S[j]]) == {"R", "B"}:
            ans += S[j+1:].count("G")
            if 2*j - i < N and S[2*j - i] == "G":
                ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N-2):
    for d in range(1, (N-i-1)//2+1):
        if {S[i], S[i+d], S[i+2*d]} == {"R", "G", "B"}:
            ans -= 1

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

n = int(input())
a = list(map(int, input().split()))
ans = 0
opp_list = []
for i in range(1, n + 1):
    opp = a[a[i - 1] - 1]
    if i == opp and i not in opp_list:
        opp_list.append(a[i - 1])
        ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(1, n + 1):
    opp = a[a[i - 1] - 1]
    if i == opp:
        ans += 1
print(ans // 2)
### BUGGY CODE ###


n, ma, mb = map(int, input().split())
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

M = 401
INF = 10 ** 15
min_cost = [[INF] * M for k in range(M)]
min_cost[0][0] = 0

for k in range(n):
    for i in range(M - 1, a[k]-1, -1):
        for j in range(M - 1, b[k] - 1, -1):
            cc = min_cost[i - a[k]][j - b[k]] + c[k]
            if cc < min_cost[i][j]:
                min_cost[i][j] = cc

res = INF
for i in range(1, M):
    for j in range(1, M):
        if i * mb == j * ma:
            if min_cost[i][j] < res:
                res = min_cost[i][j]

if res == INF:
    res = -1
print(res)


### FIXED CODE ###


n, ma, mb = map(int, input().split())
a = [0] * n
b = [0] * n
c = [0] * n
for i in range(n):
    a[i], b[i], c[i] = map(int, input().split())

M = 401
INF = 10 ** 15
min_cost = [[INF] * M for k in range(M)]
s = set()
min_cost[0][0] = 0
s.add((0, 0))

for k in range(n):
    ss = set(s)
    for i, j in reversed(sorted(s)):
        if i + a[k] < M and j + b[k] < M:
            cc = min_cost[i][j] + c[k]
            if cc < min_cost[i + a[k]][j + b[k]]:
                ss.add((i + a[k], j + b[k]))
                min_cost[i + a[k]][j + b[k]] = cc
    s = ss

res = INF
for i in range(1, M):
    for j in range(1, M):
        if i * mb == j * ma:
            if min_cost[i][j] < res:
                res = min_cost[i][j]

if res == INF:
    res = -1
print(res)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
gcd_sum = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            gcd_sum += gcd(a, b, c)
print(gcd_sum)

### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        gcd_ab = gcd(a, b)
        for c in range(1, k + 1):
            ans += gcd(gcd_ab, c)
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from functools import reduce
from operator import mul

MOD = 10 ** 9 + 7

def nCr(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))

def nHr(n, r):
    return nCr(n + r - 1, r)

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

factors = defaultdict(int)
i = 2
while M > 1:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1

ans = 1
for n in factors.values():
    ans *= nHr(N, n)
    ans %= MOD
print(ans)


### FIXED CODE ###

from collections import defaultdict
from functools import reduce
from operator import mul

MOD = 10 ** 9 + 7

def nCr(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(1, r + 1))

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

factors = defaultdict(int)
i = 2
while M > 1 and i * i <= M:
    while M % i == 0:
        M //= i
        factors[i] += 1
    i += 1 if i == 2 else 2
if M > 1:
    factors[M] += 1

ans = 1
for n in factors.values():
    ans *= nCr(N + n - 1, n)
    ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
xyz = [[] for i in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append(y)
    xyz[y].append(x)
    
ans = 0
visited = [False]*(n+1)
for x in range(1, n+1):
    if visited[x]:
        continue

    que = deque(xyz[x])
    while len(que) > 0:
        y = que.popleft()
        visited[y] = True
        for yn in xyz[y]:
            if not visited[yn]:
                que.append(yn)
    ans += 1
    
# print(visited)
print(ans)


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
xyz = {i:[] for i in range(1, n+1)}
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append((x, y, z))
    xyz[y].append((y, x, z))

connects = [0]*(n+1)
group = 1
for i in range(1, n+1):
    if connects[i] > 0:
        continue
    if len(xyz[i]) == 0:
        connects[i] = group
        group += 1
        continue

    que = deque(xyz[i])
    connects[i] = group
    while len(que) > 0:
        x, y, z = que.popleft()
        connects[y] = group
        for xn, yn, zn in xyz[y]:
            if connects[yn] > 0:
                pass
            else:
                que.append((xn, yn, zn))
    group += 1
    
# print(connects)
print(max(connects))