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

N,K=map(int,input().split())
H=list(map(int,input().split()))
DP=[0]*(N+1)
for i in range(2,N+1):
  L=[DP[i-j-1]+abs(H[i-1]-H[i-j-2])for j in range(min(K,i-1))]
  DP[i]=min(L)
print(DP[-1])

### FIXED CODE ###

N, K = map(int, input().split())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def DFS(v, parent):
  global v_count
  for u in adj[v]:
    if u != parent:
      v_count[u] += v_count[v]
      DFS(u,v)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)# aがbの親とは限らないため

for j in range(Q):
  p, x = map(int, input().split())
  v_count[p-1] += x

# 0起点に親ノードの数字を子ノードに足していく
DFS(0, -1)# 現在のノード, 親ノード
print(*v_count)


### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6)

def DFS(v, parent):
  for u in adj[v]:
    if u != parent:
      v_count[u] += v_count[v]
      DFS(u,v)

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

adj = [[] for _ in range(N)]
v_count = [0] * N

for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)# aがbの親とは限らないため

for j in range(Q):
  p, x = map(int, input().split())
  v_count[p-1] += x

# 0起点に親ノードの数字を子ノードに足していく
DFS(0, -1)# 現在のノード, 親ノード
print(*v_count)
### BUGGY CODE ###

k,s=map(int, input().split())
count=0

for x in range(k+1):
  for y in range(k+1):
    for z in range(k+1):
      if x+y+z==s:
        count+=1

print(count)



### FIXED CODE ###

k,s=map(int, input().split())
count=0

for x in range(k+1):
  for y in range(k+1):
    if 0<=s-x-y<=k:
      count+=1
    

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

#!/usr/bin/env python3

def main():
    N = int(input())
    a = [0] + list(map(int,input().split()))
    d = [0] + [a.count(i+1) for i in range(10**5)]
    Q = int(input())
    s = sum(a)
    for _ in range(Q):
        B,C = map(int,input().split())
        if d[B] != 0:
            tmp = d[B]
            d[B] = 0
            d[C] += tmp
            s = s - tmp*B + tmp*C
        print(s)




if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter

def main():
    N = int(input())
    a = list(map(int,input().split()))
    l = Counter(a)
    d = [0] + [l[i+1] for i in range(10**5)]
    Q = int(input())
    s = sum(a)
    for _ in range(Q):
        B,C = map(int,input().split())
        if d[B] != 0:
            tmp = d[B]
            d[B] = 0
            d[C] += tmp
            s = s - tmp*B + tmp*C
        print(s)




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

n,p=map(int,input().split())
a=[i for i in range(p+1)]
a[1]=0
b=int(p**0.5)
for j in a:
    if j>b:
        break
    elif j==0:
        continue
    for k in range(2*j,p+1,j):
        a[k]=0
c=[l for l in a if l!=0]
for m in range(len(c)):
    d=0
    while p%c[m]==0:
        p//=c[m]
        d+=1
    c[m]=[c[m],d]
e=1
for v in c:
    e*=v[0]**(v[1]//n)
print(e)

### FIXED CODE ###

n,p=map(int,input().split())
if n==1:
    print(p)
    quit()
a=[i for i in range(int(p**(1/n))+1)]
a[1]=0
b=int(p**0.5)
for j in a:
    if j>b:
        break
    elif j==0:
        continue
    for k in range(2*j,len(a),j):
        a[k]=0
c=[l for l in a if l!=0]
for m in range(len(c)):
    d=0
    while p%c[m]==0:
        p//=c[m]
        d+=1
    c[m]=[c[m],d]
e=1
for v in c:
    e*=v[0]**(v[1]//n)
print(e)
### BUGGY CODE ###

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

w = [-1 for i in range(N)]
v = [-1 for i in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())
    
dp = [[0 for i in range(W+1)] for j in range(N)]

#荷物を1つだけ入れた状態で、各許容重量の最大値を初期値として持たせる
for i in range(w[0],W+1):
    dp[0][i] = v[0]

for i in range(1,N):
    for j in range(W+1):
        #
        if j < w[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])
'''
for i in range(N):
    print(dp[i])
'''

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


### FIXED CODE ###

from itertools import accumulate

def chk(samp):
    for i in samp:
        print(samp)

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

w = [0 for i in range(N)]
v = [0 for i in range(N)]

for i in range(N):
    w[i],v[i]=map(int,input().split())



#価値毎に置き換える
wl = [[] for i in range(4)]

#価値ごとのりすとに入れていく
for i in range(N):
    wl[w[i]-w[0]].append(v[i])


#ソートして最初に0を追加する。0は選択しない場合
for i in range(4):
    wl[i].sort(reverse = 1)
    wl[i].insert(0,0)
    

#累積和を作る
for i in range(4):
    wl[i] = list(accumulate(wl[i]))
    
#出力用変数
out = 0


for i,wl0 in enumerate(wl[0]):
   for j,wl1 in enumerate(wl[1]):
       for k,wl2 in enumerate(wl[2]):
           for l,wl3 in enumerate(wl[3]):
               if i*(w[0])+j*(w[0]+1)+k*(w[0]+2)+l*(w[0]+3) > W:
                   pass
               else:
                   out = max(out,wl0+wl1+wl2+wl3)
                   
print(out)
### BUGGY CODE ###

from heapq import heappush, heappop

INT_MAX = 10 ** 9


def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  g = [[0] * (n+1) for i in range(n+1)]
  gp = [INT_MAX] * (n+1)
  gf = [0] * (n+1)
  
  for a, b in ab:
    g[a][b] = 1
    g[b][a] = 1
  
  h = [(0, 1, 1)]
  
  while h:
    p, a, b = heappop(h)
    if p < gp[a]:
      gp[a] = p
      gf[a] = b
    else:
      continue
    for z in range(1, n+1):
      if g[a][z]:
        heappush(h, (p + g[a][b], z, a))
  
  r = gf[2:]
  s = 'Yes' if all(0 < i < INT_MAX for i in r) else 'No'
  print(s)
  if s == 'Yes':
    for i in r:
      print(i)
  
  
  
if __name__ == '__main__':
  main()


### FIXED CODE ###

from collections import deque

def main():
  n, m = map(int, input().split())
  ab = (map(int, input().split()) for i in range(m))
  
  ggg = [[] for i in range(n+1)]
  ff = [0] * (n+1)
  
  for a, b in ab:
    ggg[a].append(b)
    ggg[b].append(a)
    
  qq = deque()
  qq.append(1)
  ff[1] = 1
  
  while qq:
    a = qq.popleft()
    for b in ggg[a]:
      if not ff[b]:
        ff[b] = a
        qq.append(b)
  
  rr = ff[2:]
  y = all(rr)
  
  print('Yes' if y else 'No')
  if y:
    for r in rr:
      print(r)

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

N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=DPsum[i-1]+DP[i]
print(DP[N]%m)


### FIXED CODE ###

N,K = map(int,input().split())
DP = [0]*(N+1)
DPsum=[0]*(N+1)
DP[1]=1
DPsum[1]=1
lr = []
m=998244353
for _ in range(K):
    l,r = map(int,input().split())
    lr.append([l,r])

for i in range(2,N+1):
    for l,r in lr:
        lx = i - r - 1
        rx = i - l
        lx = max(0,lx)
        rx = max(0,rx)
        DP[i]+= DPsum[rx]-DPsum[lx]
    DPsum[i]=(DPsum[i-1]+DP[i])%m
print(DP[N]%m)
### BUGGY CODE ###

import bisect
k,s=map(int,input().split())
ans=0
z=[i for i in range(k+1)]
for x in range(k+1):
    for y in range(k+1):
        a=s-x-y
        if a<=k and z[bisect.bisect_left(z,a)]==a:
            ans+=1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        z=s-x-y
        if 0<=z<=k:
            ans+=1
print(ans)
### BUGGY CODE ###

N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
q=[]
for i in range(0,N):
  q+=[p[i][0]]*p[i][1]
print(q[K-1])


### FIXED CODE ###

import sys
N,K=map(int, input().split())
p=[]
for i in range (0,N):
  r=list(map(int, input().split() )) 
  p.append(r)
p.sort()
k=0
for i in range(0,N):
  k+=p[i][1]
  if k>=K:
    print(p[i][0])
    sys.exit()
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
l = [0] * N
ans = 0
count = 0
check = [False] * N

while(count <= N - 1):
    check = [False] * N
    for i in range(N):
        if l[i] < N - 1:
            to = A[i][l[i]] - 1
            if (not check[to]) and (not check[i]):
                if A[to][l[to]] - 1 == i:
                    l[i] += 1
                    l[to] += 1
                    check[to] = True
                    check[i] = True
                if l[i] == N - 1:
                    count += 1
                if l[to] == N - 1:
                    count += 1
    ans += 1
    if ans > N ** 2:
        print(-1)
        exit()
    # print(l, ans)

print(ans)


### FIXED CODE ###

import sys
import time
def input():
    return sys.stdin.readline()
 
def main():
    a = time.time()
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    l = [0] * N
    ans = 0
    count = 0
    check = [False] * N
    tmpl = []
    next = False
 
    while(count < N):
        check = [False] * N
        for i in range(N):
            if l[i] < N - 1:
                to = A[i][l[i]] - 1
                if (not check[to]) and (not check[i]):
                    if A[to][l[to]] - 1 == i:
                        l[i] += 1
                        l[to] += 1
                        check[to] = True
                        check[i] = True
                        next = True
                    if l[i] == N - 1:
                        count += 1
                    if l[to] == N - 1:
                        count += 1
        ans += 1
        if not next:
            print(-1)
            exit()
        next = False

        b = time.time()
        if b - a >= 1.7:
            print(N*(N - 1)//2)
            exit()
        # print(l, ans)
 
    print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

def visit_tree(now, num):
    if not visited[now]:
        visited[now] = num
        for i in range(len(tree[now])):
            visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

def visit_tree(now, num):
    visited[now] = num
    for i in range(len(tree[now])):
        if not visited[tree[now][i]]:
            visit_tree(tree[now][i], num)

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

visited = [0 for _ in range(n)]
num = 0
for i in range(n):
    if not visited[i]:
        num += 1
        visit_tree(i, num)

print(num)
### BUGGY CODE ###

inp = list(map(int, input().split(" ")))
N, K = inp[0], inp[1]
h_arr = list(map(int, input().split(" ")))
dp = [9999999 for _ in range(N)]
dp[0] = 0
dp[1] = abs(h_arr[1]-h_arr[0])

for i in range(2, N):
	dp[i] = min([abs(h_arr[i]-h_arr[i-j]) + dp[i-j] for j in range(1, min(i+1, K+1))])
print(dp[-1])

### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 遅すぎる！
import math
import sys


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

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

x = [list(input()) for i in range(h)]

#print(x)
x[ch-1][cw-1]='a'

def tansaku():
    nu = 0
    while 1:
        nutta=0 # 塗ったマス
        for i in range(h):
            for j in range(w):
                if x[i][j] == 'a':
                    if i>0:
                        if x[i-1][j]=='.':
                            nutta += 1
                            x[i-1][j]='a'
                    if j>0:
                        if x[i][j-1]=='.':
                            nutta += 1
                            x[i][j-1]='a'
                    if i<h-1:
                        if x[i+1][j]=='.':
                            nutta += 1
                            x[i+1][j]='a'
                    if j<w-1:
                        if x[i][j+1]=='.':
                            nutta += 1
                            x[i][j+1]='a'
        if nutta==0:
            return nu
        else:
            nu += nutta

def warp():
    y = [[0 for j in range(w)] for i in range(h)]
    nu = 0
    for i in range(h):
        for j in range(w):
            if x[i][j] == 'a':
                for p in range(max(i-2,0),min(i+3,h)):
                    for q in range(max(j-2,0),min(j+3,w)):
                        if x[p][q] == '.':
                            y[p][q]='a'
                            #print("a",p,q)
                            nu += 1
    for i in range(h):
        for j in range(w):
            if y[i][j]=='a':
                x[i][j]='a'
                #print("b")
    return nu # これは塗った数よりは多いがnuが1なら0ではない


answer = 0
while(1):
    #print(x,ch,cw,dh,dw)
    nurioe = tansaku()
    #print(x,nurioe)
    if x[dh-1][dw-1]=='a':
        print(answer)
        break
    nurioe = warp()
    answer += 1
    #print(x,nurioe)
    if nurioe == 0:
        print(-1)
        break
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
#
import math
import sys

from collections import deque

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

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]

#print(maze)

q = deque([(ch+1,cw+1)])
temp[ch+1][cw+1]=0

opt = [(0,1),(0,-1),(1,0),(-1,0)]

while q:
    y,x = q.popleft()
#    print(y,x)
    # aruki
    for i in opt:
        ty,tx = y+i[0], x+i[1]
        if maze[ty][tx]=='#':
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x] # ikeru
            q.appendleft((ty,tx)) # new ikeru basho tuika
    # warp
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i, x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] =  temp[y][x]+1
                q.append((ty,tx))  # 
#    print(q)


print(temp[dh+1][dw+1])
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10000000)


N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

def func(x,y,cnt):
	if dp[x][y]!=0: return dp[x][y]

	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret+=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret+=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)


print dp[0][N-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]
### BUGGY CODE ###

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

T = 0
F = 1
C = 2

s = input()
q = int(input())

query = [input().split() for l in range(q)]

# print(s,q,query)

cnt = 0

for i in range(q):
    # print(query[i])
    if query[i][T] == "1":
        cnt += 1
        continue

    # print(s)
    if cnt % 2 == 0:
        # print(query[i])
        if query[i][F] == "1":
            s = query[i][C] + s
            # print(s)
        else:
            s = s + query[i][C]

    else:
        # print(query[i])
        if query[i][F] == "1":
            # print(s)
            s = s + query[i][C]
        else:
            s = query[i][C] + s

if cnt % 2 == 0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

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

T = 0
F = 2
C = 4

s = input()
q = int(input())

cnt = 0

front = ""
back = ""

for i in range(q):
    query = input()

    if query[T] == "1":
        cnt += 1
        continue

    # モード通常
    if cnt % 2 == 0:
        if query[F] == "1":
            front +=  query[C]
        else:
            back += query[C]

    # モード反転
    else:
        if query[F] == "1":
            back += query[C]
        else:
            front +=  query[C]


# print(cnt)
# print(front)
# print(s)
# print(back)

# moji = front+s+back

if cnt % 2 == 0:
    print(front[::-1]+s+back)
    pass
else:
    print(back[::-1]+s[::-1]+front)
    # print(s[::-1])
### BUGGY CODE ###

# def max_comn_div(n, m):
#     """give max common divisor"""
#     if n > m:
#         a, b = n, m
#     else:
#         a, b = m, n
#     while b != 0:
#         a, b = b, a % b
#     return a


# a = int(input())
# b = int(input())
# print(max_comn_div(a, b))

# def euc(a, b):
#      if a % b == 0:
#          return b
#      else:
#          return euc(b, a % b)


def euc(a, b):
    return b if a % b == 0 else euc(b, a % b)


def div(n):
    """give divisors"""
    divisors = [1]
    i = 2
    while n > 1:
        if n % i == 0:
            divisors.append(i)
            while n % i == 0:
                n = n/i
        i += 1
    return divisors


a, b = map(int, input().split())
c = div(euc(a, b))
print(len(c))


### FIXED CODE ###

# def max_comn_div(n, m):
#     """give max common divisor"""
#     if n > m:
#         a, b = n, m
#     else:
#         a, b = m, n
#     while b != 0:
#         a, b = b, a % b
#     return a


# a = int(input())
# b = int(input())
# print(max_comn_div(a, b))

# def euc(a, b):
#      if a % b == 0:
#          return b
#      else:
#          return euc(b, a % b)


def euc(a, b):
    return b if a % b == 0 else euc(b, a % b)


def div(n):
    """give divisors"""
    divisors = [1]
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            divisors.append(i)
            n /= i
    if n != 1:
        divisors.append(int(n))
    return set(divisors)


a, b = map(int, input().split())
# print(euc(a, b))
c = div(euc(a, b))
# print(c)
print(len(c))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))



N, M =two_int()

key_list=[]
treasures=[]

for i in range(M):
    mon,_ =two_int()
    key_list.append(mon)
    
    temp=[0 for i in range(N)]
    for j in many_int():
        temp[N-j-1]=1
    treasures.append("".join(list(map(str,temp))))

max_index=2**N
INF=10**15

dp=[INF for i in range(max_index)]
dp[0]=0

for i in range(max_index-1):
    for j in range(M):
        new_i = int(bin(int(treasures[j],2) | i),2)
        cost = dp[i] + key_list[j]
        dp[new_i] = min(dp[new_i], cost) 

goal_index=max_index-1
if dp[goal_index]!=INF:
    print(dp[goal_index])
else:
    print(-1)



### FIXED CODE ###

import sys
input = sys.stdin.readline

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))


def main():
    N, M =two_int()

    key_list=[]
    treasures=[]
    check={}

    for i in range(M):
        mon,_ =two_int()
        temp = map(lambda x: 1<<(x-1), many_int())
        sums = sum(temp)
        
        if sums in check:
            if check[sums] > mon:
                check[sums]=mon
        else:
            check[sums]=mon
            
    for k,v in check.items():
        key_list.append(v)
        treasures.append(k)

    max_index=2**N
    INF=10**15

    dp=[INF for i in range(max_index)]
    dp[0]=0
    M=len(key_list)

    for i in range(max_index-1):
        for j in range(M):
            new_i = int(bin(treasures[j] | i),2)
            cost = dp[i] + key_list[j]
            dp[new_i] = min(dp[new_i], cost) 
        
    goal_index=max_index-1
    if dp[goal_index]!=INF:
        print(dp[goal_index])
    else:
        print(-1)

main()
### BUGGY CODE ###

K=int(input())

memo={}
def gcd(a,b):
    if a<b:
        a,b=b,a

    aa=a
    bb=b
    if (a,b) in memo.keys():
        return memo[a,b]
    while b != 0:
        a,b, = b, a%b
    memo[aa,bb]=a
    return a





memo3={}

def gcd3(a,b,c):
    if a>b:
        a,b = b,a
    if a>c:
        a,c = c,a
    if b>c:
        b,c = c,b
    if (a,b,c) in memo3.keys():
        return memo3[(a,b,c)]
    
    g = gcd(gcd(a,b),c)
    memo3[(a,b,c)]=g
    return g


sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum += gcd3(i,j,k)
print(sum)





### FIXED CODE ###

K=int(input())

memo={}
def gcd(a,b):
    if a<b:
        a,b=b,a

    aa=a
    bb=b
    if (a,b) in memo.keys():
        return memo[a,b]
    while b != 0:
        a,b, = b, a%b
    memo[aa,bb]=a
    return a





memo3={}

def gcd3(a,b,c):
    if a>b:
        a,b = b,a
    if a>c:
        a,c = c,a
    if b>c:
        b,c = c,b
    if (a,b,c) in memo3.keys():
        return memo3[(a,b,c)]
    
    g = gcd(gcd(a,b),c)
    memo3[(a,b,c)]=g
    return g


sum=0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            
            if i==j & j==k:
                sum += gcd3(i,j,k)
                continue
            if i==j & j!=k:
                sum += gcd3(i,j,k)*3
                continue
            if i!=j & j==k:
                sum += gcd3(i,j,k)*3
                continue
            sum += gcd3(i,j,k)*6
print(sum)