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

import re
import sys

s = sys.stdin.buffer.readline().rstrip().decode()
ans = 0

for i in range(1, 200001):
    tmp = str(2019*i)
    if tmp in s:
        index = -1
        while True:
            index = s.find(tmp, index + 1)
            if index == -1:
                break
            ans += 1
    if int(tmp) > int(s):
        break
print(ans)


### FIXED CODE ###

import sys

s = sys.stdin.buffer.readline().rstrip().decode()
MOD = 2019
ans = [1] + [0 for i in range(MOD)]
t = 1
r = 0
for i in reversed(s):
    r = (r + int(i)*t) % MOD
    t = t*10%2019
    ans[r] += 1
print(sum([m*(m-1)//2 for m in ans]))
### BUGGY CODE ###

import sys

n=int(input())
ls=list(map(int,input().split()))
ls.sort()
end_k=ls[len(ls)//2]

cnt=0

for i in range(end_k):
    num=0
    for j in range(n):
        if ls[j]>i:
            num+=1
    if num==n//2:
        cnt+=1

print(cnt)


### FIXED CODE ###

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

print(ls[n//2]-ls[n//2-1])
### BUGGY CODE ###

def main():
    def sum(i):
        s=0
        while i:
            s+=tree[i]
            i-=i&-i
        return s
    def add(i,x):
        while i<=size:
            tree[i]+=x
            i+=i&-i
    n,*a=map(int,open(0).read().split())
    size=n-~n
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=(ok+ng)//2
        tree=[0]*-~size
        c=n+1
        s=0
        add(c,1)
        for t in a:
            c+=1if t>=mid else-1
            s+=sum(c)
            add(c,1)
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

### FIXED CODE ###

class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
n,*a=map(int,open(0).read().split())
m=n*-~n//2+1>>1
ng=max(a)+1
ok=0
while ng-ok>1:
    mid=(ok+ng)//2
    b=BIT(n-~n)
    c=n+1
    s=0
    b.add(c,1)
    for t in a:
        c+=1if t>=mid else-1
        s+=b.sum(c)
        b.add(c,1)
    if s>=m:ok=mid
    else:ng=mid
print(ok)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    mod = 10**9+7
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    for n in range(N):
        c = S[N-n-1]
        for i in range(10):
            if c == "?" or int(c) == i:
                for j in range(13):
                    dp[n+1][(j + i*10**n) % 13] += dp[n][j] % mod
    print(dp[N][5] % mod)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    S = input().strip()
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] = 1
    m = 1
    for n in range(N):
        c = S[N-n-1]
        if c == "?":
            for i in range(10):
                for j in range(13):
                    dp[n+1][(j + i*m)%13] += dp[n][j]
        else:
            k = int(c)
            for j in range(13):
                dp[n+1][(j + k*m)%13] += dp[n][j]
        for i in range(13):
            dp[n+1][i] %= 10**9+7
        m = m * 10 % 13
    print(dp[N][5])


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

l,r = map(int,input().split())
cnt = 0
mod_list = []
for i in range(l,r):
    for j in range(i+1,r+1):
        mod_list.append(i*j%2019)
        cnt += 1
        if cnt == 2019**2:
            break
print(min(mod_list))

### FIXED CODE ###

l,r = map(int,input().split())
cnt = 0
mod_list = []
if r- l >=2019:
    print(0)
else:
    for i in range(l,r):
        for j in range(i+1,r+1):
            mod_list.append(i*j%2019)
    print(min(mod_list))
### BUGGY CODE ###

N = int(input())

A = list(input().split())

for i in range(1,N+1):
  print(A.count(str(i)))

### FIXED CODE ###

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

import sys
import math
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
X = rl()
MOD = 10 ** 9 + 7
limit = math.factorial(N-1)
last = X[-1]
X = [last - x for x in X] #最後までの距離
answer = 0
for i in range(1, N):
    answer += X[i-1] * (limit // i)%MOD
    answer %= MOD

print(answer)



### FIXED CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

MOD = 10 ** 9 + 7
U = 10 ** 5 + 10 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
N = ir()
X = np.array(lr())

inv = np.zeros(U, np.int64)
inv[1:] = fact_inv[1:] * fact[:-1] % MOD
coef = inv[1:N].cumsum() % MOD
answer = (np.diff(X) * coef % MOD).sum() % MOD
answer *= fact[N-1]
print(answer % MOD)
# 35
### BUGGY CODE ###

N,X,Y = map(int,input().split())
ans = [0]*(N-1)
for i in range(1,N):
  for j in range(i+1,N+1):
    if i <= X and j <= X:
      dic = j-i
    elif i >= Y and j >= Y:
      dic = j-i
    elif i <= X and j >= Y:
      dic = (j-i)-(Y-X)+1
    elif X < i < Y and j >= Y:
      dic = min(i-X+1,Y-i)+(j-Y)
    elif i<=X and X < j < Y:
      dic = (X-i)+min(Y-j+1,j-X)
    elif X < i < Y and X < j < Y:
      dic = min(j-i,(i-X+1)+(Y-j))
    ans[dic-1] = ans[dic-1]+1

for ret in ans:
  print(ret)

### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n-1)


def f(N,X,Y):
  for i in range(1,N):
    for j in range(i+1,N+1):
      if i <= X and j <= X:
        dic = j-i
      elif i >= Y and j >= Y:
        dic = j-i
      elif i <= X and j >= Y:
        dic = (j-i)-(Y-X)+1
      elif X < i < Y and j >= Y:
        dic = min(i-X+1,Y-i)+(j-Y)
      elif i<=X and X < j < Y:
        dic = (X-i)+min(Y-j+1,j-X)
      elif X < i < Y and X < j < Y:
        dic = min(j-i,(i-X+1)+(Y-j))
      ans[dic-1] = ans[dic-1]+1
  
f(n,x,y)
for ret in ans:
  print(ret)
### BUGGY CODE ###

from itertools import product
from bisect import bisect
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        for i,(x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                xcost = min(xcost, abs(x - lx))
                ycost = min(ycost, abs(y - ly))
            xc[s][i] = xcost * p
            yc[s][i] = ycost * p

    def chmin(i, val):
        if ans[i] > val: ans[i] = val

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            chmin(k, sum(min(xc[xs][i], yc[s - xs][i]) for i in range(n)))
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    xc = [[0] * n for _ in range(1 << n)]
    yc = [[0] * n for _ in range(1 << n)]
    for s in range(1 << n):
        xcs = xc[s]
        ycs = yc[s]
        for i, (x, y, p) in enumerate(xyp):
            xcost = abs(x)
            ycost = abs(y)
            for j, (lx, ly, _) in enumerate(xyp):
                if s >> j & 1 == 0: continue
                if abs(x - lx) < xcost: xcost = abs(x - lx)
                if abs(y - ly) < ycost: ycost = abs(y - ly)
            xcs[i] = xcost * p
            ycs[i] = ycost * p
    # print(xc)

    ans = [inf] * (n + 1)
    for s in range(1 << n):
        k = bin(s).count("1")
        xs = (1 << n) - 1
        while xs > 0:
            xs &= s
            xcs = xc[xs]
            ycs = yc[s - xs]
            cur = 0
            for i in range(n): cur += min(xcs[i], ycs[i])
            if cur < ans[k]: ans[k] = cur
            xs -= 1

    for a in ans: print(a)

inf = 10 ** 16
n = II()
xyp = LLI(n)

solve()
### BUGGY CODE ###

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

relation = [[] for _ in range(N+1)]

for _ in range(M) :
	X, Y, Z = map(int, input().split())
	relation[X].append(Y)
	relation[Y].append(X)

visited = [False] * (N + 1)

def dfs(init) :
	queue = [init]

	while queue :
		x_ = queue.pop(0)
		visited[x_] = True

		for y_ in relation[x_] :
			if not visited[y_] :
				queue.append(y_)

# 閉路ごとdfs実行
n_closed = 0
for i in range(1, N + 1) :
	if len(relation[i]) and not visited[i] :
		n_closed += 1
		dfs(i)

print(n_closed + visited.count(False) - 1)


### FIXED CODE ###

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

parent = [-1] * (N + 1)

def root(x):
	while parent[x] >= 0:
		x = parent[x]
	return x

def unite(x,y):
	root_x = root(x)
	root_y = root(y)

	if root_x != root_y :
		if parent[root_x] > parent[root_y] :
			parent[root_x]=root_y
		else :
			if parent[root_x] == parent[root_y] :
				parent[root_x] -= 1
			parent[root_y] = root_x
    
	return

for _ in range(M) :
	X, Y, Z = map(int, input().split())
	unite(X, Y)
	
print(sum(i < 0 for i in parent) - 1)
### BUGGY CODE ###

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

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

dices = p[:k]

def exp(n):
    return n*0.5 + 0.5

def exp_list(l):
    total = 0
    for n in l:
        total += exp(n)
    return total

ans = exp_list(dices)

for i in range(1,n-k+1):
    del dices[0]

    dices.append(p[i+k-1])

    tmp = exp_list(dices)

    if tmp > ans:
        ans = tmp

print(ans)

### FIXED CODE ###

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

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

def exp(n):
    return n*0.5 + 0.5

ans = 0
for i in range(k):
    ans += p[i]
    tmp = ans

for i in range(n-k):
    tmp = tmp - p[i] + p[i+k]
    if tmp > ans:
        ans = tmp

print(ans*0.5 + k*0.5)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * N
dp[0] = 0
temp = [10**4] * K


for n in range(1, N):
	#print(dp)
	if n < K:
		for k in range(n):
			temp[k] = dp[k] + abs(h[n] - h[k])
			
	else:
		for k in range(K):
			temp[k] = dp[n - k - 1] + abs(h[n] - h[n - k - 1])
	dp[n] = min(temp)
	#print(temp)

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

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * N
dp[0] = 0
temp = [10**4] * K


for n in range(1, N):
	#print(dp)
	if n < K:
		for k in range(n):
			temp[k] = dp[k] + abs(h[n] - h[k])
			
	else:
		for k in range(K):
			temp[k] = dp[n - k - 1] + abs(h[n] - h[n - k - 1])
	dp[n] = min(temp)
	#print(temp)

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

def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


N, M, L = map(int, input().split()) 
d = [[float('inf') for _ in range(N)] for _ in range(N)]
D = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(M):
    A, B, C = map(int, input().split())
    d[A-1][B-1] = C
    d[B-1][A-1] = C
for i in range(N):
    d[i][i] = 0
d = warshall_floyd(d)

for i in range(N):
    for j in range(N):
        if 0 < d[i][j] <= L:
            D[i][j] = 1
        elif d[i][j] == 0:
            D[i][j] = 0
D = warshall_floyd(D)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    print(D[s-1][t-1] - 1 if D[s-1][t-1] != float('inf') else -1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d


N, M, L = map(int, input().split())
INF = 10 ** 10
d = [[INF for _ in range(N)] for _ in range(N)]
D = [[INF for _ in range(N)] for _ in range(N)]

for i in range(N):
    d[i][i] = 0
for i in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    d[A][B] = C
    d[B][A] = C
d = warshall_floyd(d)

for i in range(N):
    for j in range(N):
        if 0 < d[i][j] <= L:
            D[i][j] = 1
        elif d[i][j] == 0:
            D[i][j] = 0
D = warshall_floyd(D)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    print(D[s][t] - 1 if D[s][t] != INF else -1)
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(map(int, input().split()))
inf = 10 ** 8
dp = [inf] * n
dp[0] = 0

for j in range(1, n):
    buf = [dp[i] + abs(s[j]-s[i]) for i in range(max(0, j - k), j)]
    dp[j] = min(buf)
print(dp[-1])


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    s = list(map(int, input().split()))
    inf = 10 ** 8
    dp = [inf] * n
    dp[0] = 0

    for j in range(1, n):
        buf = [dp[i] + abs(s[j]-s[i]) for i in range(max(0, j - k), j)]
        dp[j] = min(buf)
    print(dp[-1])

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

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def p(n,k):
    if n<k:
        return 0
    return math.factorial(n)//math.factorial(n-k)
def dfs(cur,par=-1):
    res = 1
    c = 0 if par == -1 else 1
    cnt = len(g[cur]) - c
    for v in g[cur]:
        if v == par:
            continue
        res *= dfs(v,cur)
        res %= mod
    return res*p(k-c-1,cnt)
print(dfs(0,-1)*k%mod)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

# class Combination:
#     """
#     comb = Combination(1000000)
#     print(comb(5, 3))  # 10
#     """
#     def __init__(self, n_max, mod=10**9+7):
#         self.mod = mod
#         self.modinv = self.make_modinv_list(n_max)
#         self.fac, self.facinv = self.make_factorial_list(n_max)

#     def __call__(self, n, r):
#         return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

#     def make_factorial_list(self, n):
#         # 階乗のリストと階乗のmod逆元のリストを返す O(n)
#         # self.make_modinv_list()が先に実行されている必要がある
#         fac = [1]
#         facinv = [1]
#         for i in range(1, n+1):
#             fac.append(fac[i-1] * i % self.mod)
#             facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
#         return fac, facinv

#     def make_modinv_list(self, n):
#         # 0からnまでのmod逆元のリストを返す O(n)
#         modinv = [0] * (n+1)
#         modinv[1] = 1
#         for i in range(2, n+1):
#             modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
#         return modinv


n,k = inpl()
g = [[] for i in range(n)]
seen = [-1]*n
for i in range(n-1):
    a,b = inpl()
    g[a-1].append(b-1)
    g[b-1].append(a-1)
def p(n,i):
    count = 1
    for _ in range(i):
        count = count * n % mod
        n -= 1
    return count
def dfs(cur,par=-1):
    res = 1
    c = 0 if par == -1 else 1
    cnt = 0
    for v in g[cur]:
        if v == par:
            continue
        cnt += 1
        res *= dfs(v,cur)
        res %= mod
    return res*p(k-c-1,cnt)
print(dfs(0,-1)*k%mod)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
for i in range(n):
  li[i] -= i+1
li.sort()
ans = 10**15
for i in range(n):
  ans = min(ans,i*li[i]-sum(li[:i])+sum(li[i:])-(n-i)*li[i])
print(ans)

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
for i in range(n):
  li[i] -= i+1
li.sort()
if n%2 == 0:
  print(sum(li[int(n/2):])-sum(li[:int(n/2)]))
else:
  tmp = int((n-1)/2)
  print(sum(li[tmp+1:])-sum(li[:tmp]))
### BUGGY CODE ###

x=input()
while "ST" in x:
  x.strip("ST")
print(len(x))

### FIXED CODE ###

x = list(input())
c = 0
for i in x:
  if i == "S":
    c += 1
  elif c>0:
    c -= 1
print(2*c)
### BUGGY CODE ###

n = int(input())
N = int(n * 0.5)
total = n-1
for i in range(1,N):
    if n % i == 0:
        total_ = i + n / i - 2
    if total_ < total:
        total = total_
print(int(total))

### FIXED CODE ###

import math
n = int(input())
m = int(math.sqrt(n))
while n % m != 0:
  m -= 1
print(n//m + m -2)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,m=map(int, input().split())
    if m==0:
        print(0,0)
    else:
        ansl=[[] for i in range(n)]
        for i in range(m):
            p,s=input().split()
            p=int(p)
            if 'AC' not in ansl[p-1]:
                ansl[p-1].append(s)
        wacnt=0
        accnt=0
        for i in range(n):
            if 'AC' in ansl[i]:
                accnt+=1
                wacnt+=len(ansl[i])-1
        print(accnt,wacnt)
resolve()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()

def resolve():
    n,m=map(int, input().split())
    if m==0:
        print(0,0)
    else:
        l=[list(input().split()) for i in range(m)]
        wacnt=[0]*n
        accheck=[False]*n
        pcnt=0
        for p,s in l:
            p=int(p)
            if accheck[p-1]:
                continue
            if s=='WA':
                wacnt[p-1]+=1
            elif s=='AC':
                accheck[p-1]=True
                pcnt+=wacnt[p-1]
        print(sum(accheck),pcnt)
resolve()
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
  moji = input()
  if moji not in S:
    S.append(moji)
  
print(len(S))

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  S.append(input())

print(len(set(S)))
### BUGGY CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    K = INT()

    gcdf = lambda *numbers: reduce(gcd, numbers)
    ans = 0
    for i in range(K):
        for j in range(K):
            for k in range(K):
                ans += gcdf(i + 1, j + 1, k + 1)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    K = INT()

    gcdf = lambda *numbers: reduce(gcd, numbers)
    ans = 0
    for t in list(combinations_with_replacement(range(K), 3)):
        k = 3
        if t[0] == t[1] and t[1] == t[2] and t[2] == t[0]:
            k = 1
        elif t[0] != t[1] and t[1] != t[2] and t[2] != t[0]:
            k = 6

        ans += k * gcdf(t[0] + 1, t[1] + 1, t[2] + 1)

    print(ans)


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




S = input()
Q = int(input())

order = 1

ans = S
for i in range(Q):
    tfc = list(map(str, input().split()))

    if tfc[0] == "1":
        order *= -1
    else:
        if order == 1:
            if tfc[1] == "1":
                ans = tfc[2] + ans
            else:
                ans = ans + tfc[2]

        else:
            if tfc[1] == "2":
                ans = tfc[2] + ans
            else:
                ans = ans + tfc[2]


if order == 1:
    print(ans)
else:
    print(ans[::-1])

### FIXED CODE ###

from collections import deque



def main():
    S = input()
    Q = int(input())

    order = 1

    ans = deque()
    for i in range(len(S)):
        ans.append(S[i])

    for i in range(Q):
        tfc = list(map(str, input().split()))

        if tfc[0] == "1":
            order *= -1
        else:
            if order == 1:
                if tfc[1] == "1":
                    #ans = tfc[2] + ans
                    ans.appendleft(tfc[2])
                else:
                    #ans = ans + tfc[2]
                    ans.append(tfc[2])

            else:
                if tfc[1] == "2":
                    #ans = tfc[2] + ans
                    ans.appendleft(tfc[2])
                else:
                    #ans = ans + tfc[2]
                    ans.append(tfc[2])


    ans = "".join(ans)

    if order == 1:
        print(ans)
    else:
        print(ans[::-1])

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

import itertools
N,M = map(int,input().split())
A = []
S = [[] for _ in range(M)]
 
for m in range(M):
  a,b = map(int,input().split())
  A.append([a,b])
  S[m] = a

S = set(S)
A = [a for a in A if (a[0] in S) and (a[1] in S)]

ans = []
XX = [[] for _ in range(1<<len(A))]
X = A.copy()
i = 0
for _ in range(N-1):
  for x,v in itertools.product(X,A):   
    if x[-1] == v[0]:
      if v[1] in x:
        ans.append(x+[v[1]])
        ans[0] = [len(ans[0])-1] + ans[0]
        print(*ans[0][:-1])
        import sys
        sys.exit()
      else:
        #XX.append(x + [v[1]])
        XX[i] = x + [v[1]]
        i += 1
    X = [x for x in XX if x]


print(-1)


### FIXED CODE ###

def main():
  from collections import deque
  n,m,*t=map(int,open(0).read().split())
  i=[0]*n
  o=[[]for _ in range(n)]
  for a,b in zip(*[iter(t)]*2):
    o[a-1]+=b-1,
    i[b-1]+=1
  q=deque(v for v,f in enumerate(i)if f<1)
  r=[]
  while q:
    v=q.popleft()
    r+=v,
    for w in o[v]:
      i[w]-=1
      if i[w]==0:q+=w,
  print(-(len(r)==n))
main()