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

import sys
import math
#import fractions
from functools import reduce
import itertools

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

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


N = II()
l = []
for i in range(1,N+1):
    l.append(i)
ans=0

num = 3 #生成するビット数
bit_list = list(itertools.product(l, repeat=num))

for L in bit_list:
    ans += gcd_list(L)
print(ans)


### FIXED CODE ###

import sys
#import fractions
from math import gcd
import itertools

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

def gcd_list(numbers):
    return reduce(gcd, numbers)

def euclid(p,q):
    if p%q==0:
        return q
    else:
        return euclid(q,p%q)


N = II()

ans=0

for i in range(1, N+1):
    for j in range(1, N+1):
        x = gcd(i,j)
        for k in range(1, N+1):
            ans+=gcd(x,k)


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

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans
                


if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

### FIXED CODE ###

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

import sys
input = sys.stdin.readline

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans

if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
print(dp[N])

### FIXED CODE ###

N, K = map(int, input().split())
S = [list(map(int, input().split())) for _ in range(K)]

dp = [0] * (N + 1)
dp_sums = [0] * (N + 1)
dp[1] = dp_sums[1] = 1

for i in range(2,N+1):
    for l, r in S: 
        if i >= r + 1:
            dp[i] += dp_sums[i - l] - dp_sums[i - r - 1] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i > l and i < r + 1:
            dp[i] += dp_sums[i - l] 
            dp_sums[i] = dp_sums[i-1] + dp[i]
        elif i <= l:
            dp_sums[i] = dp_sums[i-1] + dp[i]
    dp[i] %= 998244353
    dp_sums[i] %= 998244353
print(dp[N])
### BUGGY CODE ###

import sys,math,copy
# import numpy as np
input = sys.stdin.readline
S = list(reversed(input().strip()))
N = len(S)

# dp = np.zeros((13), dtype=int)
# dp_ = np.zeros((13), dtype=int)
dp = [0] * 13
dp_ = [0] * 13
mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
divisor = 10 ** 9 + 7
dp_[0] = 1
mul = 1
for s in S:
    if s == '?':
        for d in range(10):
            m = mod13_list[(d * mul)]
            for pm in range(13):
                dp[mod13_list[(pm+m)]] = dp[mod13_list[(pm+m)]] + dp_[pm]

    else:
        si = int(s)
        m = mod13_list[(si * mul)]
        for pm in range(13):
            dp[mod13_list[(pm+m)]] = dp_[pm]

    # dp_ = dp % divisor
    # dp = dp * 0 # np.zeros((13), dtype=int)
    for i in range(13):
        dp_[i] = dp[i] % divisor
        dp[i] = 0
    mul = mod13_list[(mul * 10)]
print(dp_[5] % divisor)

### FIXED CODE ###

import sys,math,copy

def main():
    # import numpy as np
    input = sys.stdin.readline
    S = ''.join(reversed(input().strip()))

    # dp = np.zeros((13), dtype=int)
    # dp_ = np.zeros((13), dtype=int)
    dp = [0] * 13
    dp_ = [0] * 13
    mod13_list = [i % 13 for i in range(12 ** 2 + 1)]
    list10 = list(range(10))
    list13 = list(range(13))
    divisor = 10 ** 9 + 7
    dp_[0] = 1
    mul = 1
    for i in range(len(S)):
        s = S[i]
        if s == '?':
            for d in list10:
                m = mod13_list[(d * mul)]
                for pm in list13:
                    dp[mod13_list[(pm+m)]] += dp_[pm]

        else:
            si = int(s)
            m = mod13_list[(si * mul)]
            for pm in list13:
                dp[mod13_list[(pm+m)]] = dp_[pm]

        # dp_ = dp % divisor
        # dp = dp * 0 # np.zeros((13), dtype=int)
        for j in list13:
            dp_[j] = dp[j] % divisor
            dp[j] = 0
        mul = mod13_list[(mul * 10)]
    print(dp_[5])

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

s=input()
from collections import deque
s=deque(s)
ans=0
while len(list(s)):
  if s[0]==s[-1]:
    if len(list(s))==1:
      s.pop()
      break
    else:
      s.pop()
      s.popleft()
  else:
    if s[0]=="x" and s[-1]!="x":
      s.append("x")
      ans+=1
    elif s[0]!="x" and s[-1]=="x":
      s.appendleft("x")
      ans+=1
    elif s[0]!="x" and s[-1]!="x":
      print(-1)
      exit(0)

print(ans)


### FIXED CODE ###

s=input()
from collections import deque
s=deque(s)
ans=0
while len((s)):
  if s[0]==s[-1]:
    if len((s))==1:
      s.pop()
      break
    else:
      s.pop()
      s.popleft()
  else:
    if s[0]=="x" and s[-1]!="x":
      s.append("x")
      ans+=1
    elif s[0]!="x" and s[-1]=="x":
      s.appendleft("x")
      ans+=1
    elif s[0]!="x" and s[-1]!="x":
      print(-1)
      exit(0)

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

S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

tmp = 1
num = 0
for i in range(len(S) - 1, -1, -1):
    num += tmp * int(S[i])
    lists[num % 2019] += 1
    tmp *= 10

for i in range(2019):
    if lists[i] >= 2:
        ans += (lists[i] * (lists[i] - 1)) // 2

print(ans)


### FIXED CODE ###

S = input()

ans = 0
lists = [0 for i in range(2019)]
lists[0] += 1

num = 0
for i in range(len(S) - 1, -1, -1):
    num += pow(10, len(S) - 1 - i, 2019) * int(S[i])
    lists[num % 2019] += 1

for i in range(2019):
    if lists[i] >= 2:
        ans += (lists[i] * (lists[i] - 1)) // 2

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

N, M = map(int, input().split())
x = sorted([int(x) for x in input().split()])

diff = [0]*(M-1)
for i in range(M-1):
    diff[i] = x[i+1] - x[i]
diff.sort(reverse=True)
diff = diff[:N-1]

    
if N >= M:
    print(0)
elif N == 1:
    print(max(x)-min(x))
else:
    j = 0
    ans = 0
    for i in range(M-1):
        a = x[i+1] - x[i]
        if a in diff:
            if i - j >= 1:
                ans += x[i] - x[j]
            diff.remove(a)
            j = i+1
            if len(diff) == 0:
                ans += x[-1] - x[i+1]
                break
    print(ans)
    



### FIXED CODE ###

import sys

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

if N >= M:
    print(0)
    sys.exit()
diff = [0]*(M-1)
for i in range(M-1):
    diff[i] = x[i+1] - x[i]
diff.sort()
ans = sum(diff[:M-N])
print(ans)
### BUGGY CODE ###

n= int(input())
line= input().split(' ')
 
tot=1
for a in line:
	tot*= int(a)
if tot>10**18:
	print(-1)
else:
	print(tot)

### FIXED CODE ###

n= int(input())
line= input().split(' ')
 
tot=1

for a in line:
	if a=='0':
		tot=0
		break

if tot==1:
	for a in line:
		tot*= int(a)
		if tot>10**18:
			tot=-1
			break

print(tot)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())

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

dp=[10**9]*(N)
dp[0]=0

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

print(dp[-1])


### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input=sys.stdin.readline

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

dp=[float('inf')]*(N)

dp[0]=0
for i in range(1,N):
    
    for j in range(1,min(i,K)+1):

        dp[i]=min(dp[i],dp[i-j]+abs(l[i]-l[i-j]))

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

N = int(input())
num = []
line = input().split()
for i in range(N):
    num.append(int(line[i]))

sum = 0
for s in range(N):
    e = s + 1
    while e < N:
        result = num[s] * num[e]
        #print(str(result) + " = " + str(num[s]) + "*" + str(num[e]))
        sum += result
        e += 1
mod = 10 ** 9 + 7
print(sum % mod)

### FIXED CODE ###

N = int(input())
num_list =  [int(i) for i in input().split()]
result = 0
mod = 10 ** 9 + 7
right = sum(num_list)
for number in num_list:
    #A*B + A * C = A*(B+C)で計算
    right -= number
    result += (number * right) % mod
print(result % mod)
### BUGGY CODE ###

N, A, B, K = map(int, input().split())
mod = 998244353
f_table = [1, 1]
inverse_table = {}


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return f_table[n] * inverse(r) * inverse(n-r) % mod

  
def inverse(x):
    if x in inverse_table:
        return inverse_table[x]
    res = pow(f_table[x], mod-2, mod)
    inverse_table[x] = res
    return res


for i in range(2, N + 1):
    f_table.append((f_table[-1] * i) % mod)

res = 0
for a in range(0, N+1):
    b = (K - A*a) // B
    if (K - A * a) % B == 0 and 0 <= b <= N:
        res += cmb(N, a) * cmb(N, b) % mod
print(res % mod)


### FIXED CODE ###

import math

N, A, B, K = map(int, input().split())
mod = 998244353
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]


def cmb(n, r):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

res = 0
for a in range(0, N+1):
    b = (K - A*a) // B
    if (K - A * a) % B == 0 and 0 <= b <= N:
        res += cmb(N, a) * cmb(N, b) % mod
print(res % mod)
### BUGGY CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
temp = None
for c in range(C + 1):
    if (c == K - A - B):
        if (temp is None):
            temp = A - c
        else:
            if (temp < A - c):
                temp = A - c
print(temp)


### FIXED CODE ###

from sys import stdin
A, B, C, K = [int(x) for x in stdin.readline().rstrip().split()]
if (A >= K):
    print(K)
else:
    if (B >= (K - A)):
        print(A)
    else:
        print(2*A + B - K)
### BUGGY CODE ###

import sys
from collections import defaultdict, deque


def dfs(s, links, states):
    if s in states:
        if states[s] == 1:
            return False
    else:
        states[s] = 1
        for u in links[s]:
            result = dfs(u, links, states)
            if not result:
                return False
        states[s] = 2
    return True


n = int(input())
links = defaultdict(set)
may_root = set()
in_cnt = defaultdict(lambda: 0)
for i, line in enumerate(sys.stdin):
    aaa = list(map(int, line.split()))
    j = aaa[0] - 1
    a, b = (i, j) if i < j else (j, i)
    prev = a * 1000 + b
    may_root.add(prev)

    for j in aaa[1:]:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * 1000 + b
        links[prev].add(key)
        in_cnt[key] += 1
        prev = key
may_root = {r for r in may_root if in_cnt[r] == 0}

if not may_root:
    print(-1)
    exit()

states = {}
for key in may_root:
    result = dfs(key, links, states)
    if result == False:
        print(-1)
        exit()

q = deque([(r, 1) for r in may_root])
ans = 0
while q:
    k, d = q.popleft()
    ans = max(ans, d)
    d += 1
    q.extend((u, d) for u in links[k])
print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict


def dfs(root, links):
    status = {}
    topological = []
    q = [(r, 0, 1) for r in root]
    while q:
        node = q.pop()
        if node[1] == 0:
            v, _, d = node
            q.append((v, 1))
            status[v] = 1
            d += 1
            for u in links[v]:
                if u in status:
                    if status[u] == 1:
                        return False
                else:
                    q.append((u, 0, d))
        else:
            v = node[0]
            status[v] = 2
            topological.append(v)
    topological.reverse()
    return topological


n = int(input())
links = defaultdict(set)
may_root = set()
lines = sys.stdin.readlines()
matches = []
for i in range(n):
    line = lines[i]
    aaa = list(map(int, line.split()))
    match_order = []
    for j in aaa:
        j -= 1
        a, b = (i, j) if i < j else (j, i)
        key = a * n + b
        match_order.append(key)
    matches.append(match_order)
    may_root.add(match_order[0])

for i in range(n):
    kkk = matches[i]
    prev = kkk[0]

    for key in kkk[1:]:
        links[prev].add(key)
        may_root.discard(key)
        prev = key

if not may_root:
    print(-1)
    exit()

topological = dfs(may_root, links)
if topological == False:
    print(-1)
    exit()

ans = 0
depth = defaultdict(lambda: 1)
for v in topological:
    d = depth[v] + 1
    for u in links[v]:
        depth[u] = max(depth[u], d)

print(max(depth.values()))
### BUGGY CODE ###

N, M = map(int, input().split())
abl = []
for i in range(M):
    abl.append(list(map(int,input().split())))

island = 0
ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1:
        island = i[1]
        for v in abl:
            if v[0] == island and v[1] == N:
                ans = 'POSSIBLE'
                print(ans)
                exit()

print(ans)


### FIXED CODE ###

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

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])


for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

import math
from collections import defaultdict
d = defaultdict(str)
n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

ai = a[0]
ai_fct = math.factorial(ai)
max_fct = 0
for i in range(n):
    if (i == 0):
        continue
    fct = (ai_fct // math.factorial(a[i])) // math.factorial(ai - a[i])
    d[fct] = str(ai) + ' ' + str(a[i])
    max_fct = max(max_fct, fct)

print(d[max_fct])


### FIXED CODE ###

import bisect
n = int(input())
a = sorted(map(int, input().split()))

ai = a[-1]
half_ai = ai // 2

i_left = bisect.bisect_left(a, half_ai)
i_right = bisect.bisect_right(a, half_ai)
if (a[i_left] == half_ai):
    print(ai, half_ai)
    exit()

if (i_left == i_right and i_left == 0):
    print(ai, a[0])
    exit()

if (abs(half_ai - a[i_left - 1]) >=
        abs(half_ai - a[i_right]) and i_right != len(a) - 1):
    print(ai, a[i_right])
else:
    print(ai, a[i_left - 1])
### BUGGY CODE ###

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

t=0
c=0
for i in range(N):
    for j in range(i+1,N):
        t=A[i]+A[j]
        for k in range(j+1,N):
            if((max(A[i],A[j],A[k])*2)<(t+A[k])):
                c+=1
            else:
                break
print(c)


### FIXED CODE ###

import bisect

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

t=0
c=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=A[i]+A[j]
        num=bisect.bisect_left(A,t)-1
        c+=max((num-j),0)

print(c)
### BUGGY CODE ###

import itertools
from copy import deepcopy

def stuck(Array,Order):
	remain = len(Array)
	if remain == 0: return G(Order),Order
	minG,minOrder = 9999999,[]
	w = sum([int(Array[i][1]) for i in range(remain)])
	for i in range(remain):
		if int(Array[i][2]) >= w-int(Array[i][1]):
			array = deepcopy(Array)
			order = deepcopy(Order)
			order[n-remain] = array.pop(i)
			curG,curOrder = stuck(array,order)
			if curG < minG:
				minG = curG
				minOrder = curOrder
	return minG,minOrder

def G(array):
	nume=sum([(i+1)*int(array[i][1]) for i in range(n)])*1.0
	denomi=sum([int(array[i][1]) for i in range(n)])
	return nume/denomi
	
while 1:
	n=input()
	if n==0:break
	lunch=[raw_input().split() for i in range(n)]
	minG,ans=stuck(lunch,[0]*n)
	for i in range(n):
		print ans[i][0]

### FIXED CODE ###

def stuck(array):
	order=[]
	while array:
		r = len(array)
		w = sum([array[i][1] for i in range(r)])
		mx = 0
		for i in range(r):
			if array[i][2] >= w-array[i][1] and array[i][1] > mx:
				mx = array[i][1]
				id = i
		order.append(array.pop(id)[0])
	return order

def change(a):
	return a[0],int(a[1]),int(a[2])
	
while 1:
	n = input()
	if n == 0:break
	lunch = [change(raw_input().split()) for i in range(n)]
	ans = stuck(lunch)
	for i in range(n):
		print ans[i]
### BUGGY CODE ###

N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])
T = []
for i in range(N):
    T.append([R[i][0] + R[i][1], R[i][0] - R[i][1]])
T.sort()
while len(T) - 1 > 0:
    t = T.pop(0)
    i = 1
    while len(T) and t[0] > T[0][1]:
        N -= 1
        i += 1
        T.pop(0)
print(N)


### FIXED CODE ###

N = int(input())
X = [list(map(int, input().split())) for i in range(N)]
LR = [[x[0]-x[1], x[0] + x[1]] for x in X]
LR.sort(key=lambda x:x[1])

A = 1
right = LR[0][1]
for i in range(1, N):
    if right <= LR[i][0]:
        A += 1
        right = LR[i][1]
print(A)
### BUGGY CODE ###

N,Q=map(int,input().split())
s=input()
for i in range(Q):
  l,r=map(int,input().split())
  print(s[l-1:r].count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
s=input()
A=[0]
for i in range(N-1):
  if s[i]+s[i+1]=="AC":
    A.append(A[i]+1)
  else:
    A.append(A[i])
for i in range(Q):
  l,r=map(int,input().split())
  print(A[r-1]-A[l-1])
### BUGGY CODE ###

n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and i!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans//2)



### FIXED CODE ###

#import numpy as np
import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]
#d=np.array(d,np.int64)
#do a floyd warshall and test if something improves 
for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)
### BUGGY CODE ###

s = input()
x, y = map(int, input().split())

ss = s.split("T")
xmove = [i.count("F") for i in ss[::2]]
xfirst = xmove[0] # xの１回目はプラス方向固定のため切り出す
xmove = xmove[1:] # ２回目以降でリスト再作成
ymove = [i.count("F") for i in ss[1::2]]

lenx, leny = len(xmove), len(ymove)

# dp[i][p]: (x, y 各方向の)i回目の移動の後にpにいることができるか
dpx = [[False] * 8010 * 2 for _ in range(lenx+1)]
dpy = [[False] * 8010 * 2 for _ in range(leny+1)]

dpx[0][xfirst] = True
for i in range(lenx):
  for j in range(-8010, 8010):
    if j - xmove[i] > -8010:
      dpx[i+1][j] = max(dpx[i+1][j], dpx[i][j - xmove[i]])
    if j + xmove[i] < 8010: 
      dpx[i+1][j] = max(dpx[i+1][j], dpx[i][j + xmove[i]])

dpy[0][0] = True
for i in range(leny):
  for j in range(-8010, 8010):
    if j - ymove[i] > -8010:
      dpy[i+1][j] = max(dpy[i+1][j], dpy[i][j - ymove[i]])
    if j + ymove[i] < 8010:
      dpy[i+1][j] = max(dpy[i+1][j], dpy[i][j + ymove[i]])

if dpx[-1][x] and  dpy[-1][y]:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

def f(start, goal, steps):
  res = set([start])
  for s in steps:
    next_res = set()
    for r in res:
      next_res.add(r + s)
      next_res.add(r - s)
    res = next_res
  return goal in res

s = input()
x, y = map(int, input().split())

ss = s.split("T")
xmove = [i.count("F") for i in ss[::2]]
xfirst = xmove[0] # xの１回目はプラス方向固定のため切り出す
xmove = xmove[1:] # ２回目以降でリスト再作成
ymove = [i.count("F") for i in ss[1::2]]

if f(xfirst, x, xmove) and f(0, y, ymove):
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

n = int(input())
a_l = list(map(int, input().split()))

# 0 ~ 10**6
A_list = [True for i in range(10**6+1)]

# aのリストを作成
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# aのリストの重複削除
for i in a_l:
	if(a_l.count(i) != 1):
		A_list[i] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in range(len(a_l)):
	if(A_list[a_l[i]]):
		cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
a_l = list(map(int, input().split()))

# 0 ~ 10**6に入力値の個数を入れる
# (count()で数えると、o(n**2)になるため)
val_list = [0 for i in range(10**6+1)]
for i in a_l:
	val_list[i] += 1

# 重複削除
a_l = list(set(a_l))

# 0 ~ 10**6のリスト
A_list = [True for i in range(10**6+1)]
# 倍数のところにFalseを入れる
for i in a_l:
	for j in range(i*2, 10**6+1, i):
		A_list[j] = False

# Trueと一致するa_lの個数を数える
cnt = 0
for i in a_l:
	if(val_list[i] != 1):
		continue
	if(A_list[i]):
		cnt += 1

print(cnt)
### BUGGY CODE ###

import math
from functools import reduce

def calc(a, b, c):
    return reduce(math.gcd, [a, b, c])

def solve(k):
    count = 0
    for i in range(1, k+1):
        for j in range(1, k+1):
            for k in range(1, k+1):
                count += calc(i, j, k)

    return count

k = int(input())

print(solve(k))


### FIXED CODE ###

from math import gcd

k = int(input())

ir = range(1, k+1)
jr = range(1, k+1)
lr = range(1, k+1)

count = 0
for i in ir:
  for j in jr:
    for l in lr:
      count += gcd(i, gcd(j, l))

print(count)