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

import math
N = int(input())
f=0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            d=math.gcd(a, b)
            e=math.gcd(d, c)
            f+=e
print(f)

### FIXED CODE ###

import math
N = int(input())
f = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            if b<a or c<a or b>c:
                continue
            elif a==b and b==c:
                d=math.gcd(a, b)
                e=math.gcd(d, c)
                f+=e
                continue
            elif a==b and b!=c:
                d=math.gcd(a, b)
                e=math.gcd(d, c)
                f+=e*3
                continue
            elif b==c and b!=a:
                d=math.gcd(a, b)
                e=math.gcd(d, c)
                f+=e*3
                continue   
            elif a==c and b!=c:
                d=math.gcd(a, b)
                e=math.gcd(d, c)
                f+=e*3
                continue
            else:
                d=math.gcd(a, b)
                e=math.gcd(d, c)
                f+=e*6
                continue
print(f)
### BUGGY CODE ###

# 2019-11-13 08:30:54(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]
    a.sort()

    bc = []
    for _ in range(m):
        bi, ci = [int(x) for x in sys.stdin.readline().split()]
        bc.append([bi, ci])
    
    bc.sort(reverse=True, key=lambda x: x[1])
    
    res = []
    for i in range(m):
        if a:
            index = bi_l(a, bc[i][1])
            if index == 0:
                res += a
                break
            else:
                if index > bc[i][0]:
                    a = a[bc[i][0]:]
                    res += [bc[i][1]] * bc[i][0]
                else:
                    a = a[index:]
                    res += [bc[i][1]] * index
        else:
            break
    else:
        res += a
    print(sum(res))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-13 08:30:54(JST)
import sys
import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]

    a = list(collections.Counter(a).items())

    for _ in range(m):
        b, c = [int(x) for x in sys.stdin.readline().split()]
        a.append((c,b))
    
    a.sort(reverse=True)
    
    total = 0
    count = 0
    for i in range(n+m): # max
        select = a[i]
        for j in range(select[1], 0, -1):
            if count + j > n:
                continue
            else:
                count += j
                total += select[0] * j
                break
        if count == n:
            break
    
    print(total)

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

from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])*10**i%mod)%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)

### FIXED CODE ###

from collections import Counter
s=input()
n=len(s)
M=[0]
mod=2019
for i in range(n):
	m=(M[-1]+int(s[n-1-i])%mod*pow(10,i,mod))%mod
	M.append(m)
MC=Counter(M)
r=0
for v in MC.values():
	if v>1:
		r+=v*(v-1)//2
print(r)
### BUGGY CODE ###

n=int(input())
ans=0
for i in range(1,n):
    for j in range(1,i+1):
        if i%j==0:
            ans+=1
        
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
for a in range(1, n):
    ans+=(n - 1)//a
print(ans)
### BUGGY CODE ###

n = int(input())
l_list = list(map(int,input().split()))
l_list.sort(reverse=True)
count = 0
for a in range(n):
    for b in range(a+1,n):
        for c in range(b+1,n):
            if (l_list[a]<l_list[b]+l_list[c]):
                count += 1
print(count)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        count += bisect_left(l_list,l_list[i]+l_list[j]) - j - 1

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

n = int(input())
a = list(map(int, input().split()))
d = {}

for i in a:
    if not i in d.keys():
        d[i] = 1
        continue
    d[i] += 1
    
for j in a:
    ans = 0
    for k in d.keys():
        m = d[k]
        if j == k and m >= 3:
            ans += (m-1) * (m-2) // 2
        elif not j == k and m >= 2:
            ans += m * (m-1) // 2
    print(ans)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
t = 0

for v in c.values():
    t += v * (v-1) // 2
for i in a:
    print(t - (c[i]-1))
### BUGGY CODE ###

def digit(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans

N = int(input())

check = 100
for i in range(1, 1+N):
    if N % i != 0:
        continue
    if N // i < i:
        break
    j = N // i
    f = max(digit(i), digit(j))
    check = min(check, f)

print(check)

### FIXED CODE ###

def digit(n):
    ans = 0
    while n > 0:
        ans += 1
        n //= 10
    return ans

N = int(input())

check = 100
for i in range(1, int(1e6)):
    if N % i != 0:
        continue
    if N // i < i:
        break
    j = N // i
    f = max(digit(i), digit(j))
    check = min(check, f)

print(check)
### BUGGY CODE ###

C = int(1e9) + 7
h, w, a, b = [int(x) for x in input().split()]

# 1000000005 = 2^29 + 2^28 + 2^27 + 2^25 + 2^24 + 2^23 + 2^20 + 2^19 + 2^17 + 2^15 + 2^14 + 2^11 + 2^9 + 2^2 + 1

def pow(n):
    ans = n
    for i in range(1, 30):
        n = (n * n) % C
        if i in {29, 28, 27, 25, 24, 23, 20, 19, 17, 15, 14, 11, 9, 2}:
            ans = (ans * n) % C
    return ans

fact = [1]
factinv = [1] # dummy
for x in range(1, h + w - 2):
    fact.append((x * fact[x - 1]) % C)
    # factinv.append(pow(x)) # <- this won't work, why?
    factinv.append((pow(x) * factinv[x - 1]) % C)

def nCr(n, r):
    return (fact[n] * factinv[r] * factinv[n - r]) % C

ans = 0
for i in range(b, w):
    ans = (ans + nCr(i + h - a - 1, h - a - 1) * nCr(a - 1 + w - i - 1, a - 1)) % C

print(ans)


### FIXED CODE ###

C = int(1e9) + 7
h, w, a, b = [int(x) for x in input().split()]

# 1000000005 = 2^29 + 2^28 + 2^27 + 2^25 + 2^24 + 2^23 + 2^20 + 2^19 + 2^17 + 2^15 + 2^14 + 2^11 + 2^9 + 2^2 + 1

def pow(n):
    ans = n
    for i in range(1, 30):
        n = (n * n) % C
        if i in {29, 28, 27, 25, 24, 23, 20, 19, 17, 15, 14, 11, 9, 2}:
            ans = (ans * n) % C
    return ans

fact = [1]
factinv = [1] # dummy
for x in range(1, h + w - 2):
    fact.append((x * fact[x - 1]) % C)
    # factinv.append(pow(x)) # <- this won't work, why?
    factinv.append((pow(x) * factinv[x - 1]) % C)

def nCr(n, r):
    return (fact[n] * factinv[r] * factinv[n - r]) % C

ans = 0
for i in range(b, w):
    ans = (ans + nCr(i + h - a - 1, h - a - 1) * nCr(a - 1 + w - i - 1, a - 1)) % C

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

from functools import reduce
from fractions import gcd

n = int(input())
A = [int(a) for a in input().split()]

l = [0 for _ in range(n)]
r = [0 for _ in range(n)]
ans = []

for i in range(n):
    l[i] = reduce(gcd,[0]+A[:i])
    r[i] = reduce(gcd,A[i+1:]+[0])
    
for i in range(n):
    ans.append(gcd(l[i],r[i]))
    
print(max(ans))

### FIXED CODE ###

from functools import reduce
from fractions import gcd

n = int(input())
A = [int(a) for a in input().split()]

l = [0 for _ in range(n+1)]
r = [0 for _ in range(n+1)]
ans = []

for i in range(n):
    l[i+1] = gcd(l[i],A[i])

for i in range(n-1,-1,-1):
    r[i-1] = gcd(r[i],A[i])
    
for i in range(n):
    ans.append(gcd(l[i],r[i]))
    
print(max(ans))
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
ab=list(list(map(int,input().split())) for i in range(m))
d=deque()
d.append(1)
t=[deque() for i in range(n)]
for i in range(m):
  t[ab[i][0]-1].append(ab[i][1])
  t[ab[i][1]-1].append(ab[i][0])
h=[0]*(n-1)
u=deque()
while 0 in h:
  for i in t[d[0]-1]:
    if i in d or i in u:
      continue
    else:
      h[i-2]+=d[0]
      d.append(i)
  u.append(d[0])
  d.popleft()
print("Yes")
for i in range(n-1):
  print(h[i])

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b)
  g[b-1].append(a)
q=deque()
q.append(1)
check=[0]*n
check[0]=1
ans=[0]*n
while len(q)!=0:
  v=q.popleft()
  for u in g[v-1]:
    if check[u-1]==0:
      check[u-1]=1
      ans[u-1]=v
      q.append(u)
print("Yes")
for i in range(1,n):
  print(ans[i])
### BUGGY CODE ###

MOD = 10**9+7
MAXN = 2*10**6+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

K = int(input())
S = input()
R = len(S)
N = K + R
ans = 0
for r in range(R,N+1):
    power = pow(25, N-r, MOD)
    ans += nCr(N, r) * power % MOD
    ans %= MOD
print(ans)


### FIXED CODE ###

MOD = 10**9+7
MAXN = 2*10**6+5
f = [1]
for i in range(MAXN):
    f.append(f[-1] * (i+1) % MOD)
def nCr(n, r, mod=MOD):
    return f[n] * pow(f[r], mod-2, mod) * pow(f[n-r], mod-2, mod) % mod

K = int(input())
S = input()
R = len(S)
N = K + R
ans = 0
for r in range(R,N+1):
    power = pow(25, N-r, MOD)
    ans += nCr(N, r) * power % MOD
    ans %= MOD
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
bit = [0]*60
ans = 0
mod = 10**9+7
for i in a:
    cnt = 1
    while i:
        bit[-cnt] += i%2
        i //= 2
        cnt += 1
for i in range(60):
    ans += (n-bit[-1-i])*bit[-1-i] * pow(2,i,mod)
print(ans%mod)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
bit = [0]*60
ans = 0
mod = 10**9+7
for i in a:
    cnt = 1
    while i:
        bit[-cnt] += i%2
        i //= 2
        cnt += 1
for i in range(60):
    ans += (n-bit[-1-i])*bit[-1-i] * (2**i) % mod
    ans %= mod
print(ans)
### BUGGY CODE ###

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

s = set(a)
l = len(s)
l2 = 0 if len([a.count(x) for x in s]) % 2 else 1
print(l - l2)

### FIXED CODE ###

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

s = set(a)
l = len(s)
l2 = 0 if l % 2 else 1
print(l - l2)
### BUGGY CODE ###

n = int(input())
s = [0] * n
for i in range(n):
    s[i] = input()

li = []
ans = [0] * n
for i in range(n):
    if s[i] in li:
        ans[li.index(s[i])] += 1
    else:
        li.append(s[i])
        ans[li.index(s[i])] += 1

mx = max(ans)
m = [i for i, j in enumerate(ans) if j == mx]

a = []
for k in range(len(m)):
    a.append(li[m[k]])

a.sort()
for n in range(len(a)):
    print(a[n])

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]

dic = {}
for i in range(n):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic[s[i]] = 1

max_dic = max(dic.values())
ans = [i for i, j in dic.items() if j == max_dic]
ans.sort()

for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

import functools
import fractions
N = int(input())
A = [int(i) for i in input().split()]
S = set(A)


mod = 10**9 + 7


def multiple(a, b):
    return a*b // fractions.gcd(a, b)


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(S)

ans = 0
for a in A:
    ans += lcm//a
    # ans %= mod
print(ans % mod)


### FIXED CODE ###

import functools
import fractions
N = int(input())
A = [int(i) for i in input().split()]
S = set(A)


mod = 10**9 + 7


def multiple(a, b):
    return a*b // fractions.gcd(a, b)


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(S)

ans = 0
for a in A:
    ans += lcm//a
    # ans %= mod
print(ans % mod)
### BUGGY CODE ###

n,m,d=map(int,input().split())
#すべての組み合わせの和の平均 = すべての組み合わせからランダムに1つ選んだ時の期待値
#「期待値の線形性」とは「和の期待値は期待値の和に等しい」こと
#E[X+Y]=E[X]+E[Y]
ALL=n**m

if d==0:
    pro=1/n
else:
    pro=(2*(n-d))/n**2

ans=pro*(m-1)
print(ans)

### FIXED CODE ###

n,m,d=map(int,input().split())
#すべての組み合わせの和の平均 = すべての組み合わせからランダムに1つ選んだ時の期待値
#「期待値の線形性」とは「和の期待値は期待値の和に等しい」こと
#E[X+Y]=E[X]+E[Y]
if d==0:
    pro=1/n
else:
    pro=(2*(n-d))/n**2

ans=pro*(m-1)
print(ans)
### BUGGY CODE ###

def gcd(x,y):
    while y!=0:
        x,y=y,x%y
    else:
        return x

N=int(input())
A=[int(i) for i in input().split()]
GCD=[]
if len(A)==2:
    print(max(A))
else:
    for i in range(N):
        B=A.copy()
        B.remove(B[i])
    
        a=gcd(B[0],B[1])
        for k in range(N-3):
            a=gcd(a,B[k+2])
        GCD.append(a)
    print(max(GCD))

### FIXED CODE ###

try:
    from fractions import gcd
except:
    from math import gcd
from itertools import accumulate
N=int(input())
A=[int(i) for i in input().split()]
l=[0]+list(accumulate(A,gcd))
g=list(reversed(list(accumulate(reversed(A),gcd))))+[0]

print(max([gcd(l[i-1],g[i]) for i in range(1,N+1)]))
### BUGGY CODE ###

import sys
s = sys.stdin.readlines()
N = int(s[0])
S = s[1]
Q = int(s[2])


seg = [set([]) for _ in range(2*N-1)]
def update(k, x):
    k += N-1
    seg[k] = {x:1}
    while k:
        k = (k-1)//2
        seg[k] = set(seg[2*k+1]) | set(seg[2*k+2])
        
def query(p, q):
    p += N-1
    q += N-2
    res = set([])
    while q-p > 1:
        if p&1 == 0:
            if p >= N-1:
                seg[p] = set(seg[p])
            res = res | seg[p]
        if q&1 == 1:
            if q >= N-1:
                seg[q] = set(seg[q])
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        if q >= N-1:
            seg[q] = set(seg[q])
        res |= seg[q]
    else:
        if p >= N-1:
            seg[p] = set(seg[p])
        if q >= N-1:
            seg[q] = set(seg[q])
        res |= seg[p] | seg[q]
    return len(res)

for i in range(N):
    update(i, S[i])
    
for e in s[3:]:
    a,b,c = map(str, e.split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

### FIXED CODE ###

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

seg = [0]*(2*N-1)

def update(k, x):
    k += N-1
    seg[k] = 2**x
    while k:
        k = (k-1)//2
        seg[k] = seg[2*k+1] | seg[2*k+2]
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res |= seg[q]
    else:
        res |= seg[p] | seg[q]
    return bin(res).count("1")

def f(s):
    return ord(s) - ord("a") + 1

for i in range(N):
    update(i, f(S[i]))
    
Q = int(input())
for _ in range(Q):
    a,b,c = map(str, input().split())
    if a == "1":
        update(int(b)-1, f(c))
    else:
        print(query(int(b)-1, int(c)))
### BUGGY CODE ###

def main():
    count = int(input())
    integars = sorted(int(x) for x in input().split())
    ans = 0
    for i, x in enumerate(integars):
        chosen = True
        for j, y in enumerate(integars):
            if i == j:
                continue
            elif i + 1 < j:
                break
            elif x % y == 0:
                chosen = False
                break
        if chosen:
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    numbers = int(input())
    array = [int(x) for x in input().split()]
    maximum = 1000001
    counter = [0] * maximum

    for x in array:
        if counter[x] != 0:
            counter[x] = 2
            continue
        else:
            for multiple in range(x, maximum, x):
                counter[multiple] += 1
    ans = 0
    for x in array:
        if counter[x] == 1:
            ans += 1
    print(ans)


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

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)

#  f = open('C_input_29.txt')
#  lines = f.readlines()
#  f.close()
#  N, M = map(int, lines[0].split())
#  A = []
#  for line in lines[1:]:
#      A.append(int(line))

N, M = LI()
A = []
for i in range(M):
    A.append(_I())

if M != 0:
    # 連続した壊れた段がある場合は0
    B = [i for i in A]
    B.remove(B[0])
    B.append(10**15+100)
    diffs = [b - a for a, b in zip(A,B)]
    #  print(diffs)

    if any(i == 1 for i in diffs):
        # 隣同士なので0
        print(0)
        exit()
#  print('hoge')
"""
考え方
xにたどり着く通りは、x-1とx-2段目にたどり着く通りの合計
dp
3が障害のとき
1へは1通り
2へは0からと1からの2通り
3へは0通り
4へは2からの2通りと、3からの0通りで2通り
5へは3からの0通りと4からの2通りで2通り
6へは4からの2通りと5からの2通りで4通り
"""
dp = {}
#  print('fua')
dp[0] = 1
dp[1] = 1 if 1 not in A else 0
[dp.update({i: (dp[i-1] + dp[i-2])%mod}) if i not in A else dp.update({i: 0}) for i in range(2, N+1)]
#  for i in range(2, N+1):
#      print(i)
#      # i段目までの通りを計算する
#      if i in A:
#          # i段目が障害のときは0になっているので飛ばす
#          dp[i] = 0
#          continue
    
#      dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % mod)



### FIXED CODE ###

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

mod = 10 ** 9 + 7

def get_nums(n):
    res = [0 for _ in range(n)]
    for i in range(n):
        res[i] = int(input())
    return res


def get_numbers():
    return map(int, input().split())


n, m = get_numbers()
a = set(get_nums(m))

dp = [0 for _ in range(n + 1)]
dp[0] = 1
if 1 not in a:
    dp[1] = 1

for i in range(2, n + 1):
    if i not in a:
        dp[i] = dp[i - 1] + dp[i - 2]
        dp[i] %= mod

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

n = int(input())
blocks = []
for i in range(n):
    w_str, s_str, v_str = input().split(" ")
    w, s, v = int(w_str), int(s_str), int(v_str)
    blocks.append({"w": w, "s": s, "v": v})

def dp(blocks, max_s):
    max_val = 0
    for i in range(len(blocks)):
        taken =  blocks[i]

        # klo constraint nya
        new_max_s = 0
        if max_s is None:
            new_max_s = taken["s"]
        else:
            new_max_s = min(max_s-taken["w"], taken["s"])

        # ini constraint nya
        if new_max_s < 0:
            continue

        # remaining blocks, taruh sini, biar ga diitung kalau jelas ga mungkin
        remaining_blocks = [blocks[x] for x in range(len(blocks)) if x != i]

        # ini nilai tambahan
        taken_val = taken["v"]
        new_val = taken_val + dp(remaining_blocks, new_max_s)
        if new_val > max_val:
            max_val = new_val

    return max_val

print(dp(blocks, None))

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
N = int(input())
WSV = list(tuple(map(int, input().split())) for _ in range(N))
WSV.sort(key=lambda x: x[0] + x[1])
U = 2 * 10 ** 4 + 100
dp = np.zeros(U, dtype=np.int64)
for w, s, v in WSV:
    dp[w:w+s+1] = np.maximum(dp[w:w+s+1], dp[:s+1] + v)
print(dp.max())
### BUGGY CODE ###

from collections import deque
S = input()
S  = deque(S)
Q = int(input())

for _ in range(Q):
    string = (input())
    Query = string.replace(' ', '')
    Query = list(Query)

    if Query[0] == "1":
        S = list(S)
        S = S[::-1]
        S= deque(S)
    else:
        if Query[1] == "1":
            S.appendleft(Query[2])
        else:
            S.append(Query[2])

S = list(S)
ans = "".join(S)
print(ans)


### FIXED CODE ###

from collections import deque
S = input()
S  = deque(S)
Q = int(input())

# 0の時は普通、1の時は反転状態
Reverse_Flag = 0  

for _ in range(Q):
    string = (input())
    Query = string.replace(' ', '')
    Query = list(Query)

    if Query[0] == "1":
        if Reverse_Flag == 0:
            Reverse_Flag = 1
        else:
            Reverse_Flag = 0
    
    elif  Query[1] == "1":
        if Reverse_Flag == 0:
            S.appendleft(Query[2])
        else:
            S.append(Query[2])

    else:
        if Reverse_Flag == 0:
            S.append(Query[2])
        else:
            S.appendleft(Query[2])

if Reverse_Flag == 1:
    S = list(S)
    S = S[::-1]
    print("".join(S))
else:
    S = list(S)
    print("".join(S))
### BUGGY CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n=int(input())
a=prime_factorize(n)
x=len(a)
m=float("inf")
for bit in range(1<<x-1):
    ai=1
    bi=1
    for i in range(x):
        if bit&(1<<i):
            ai*=a[i]
        else:
            bi*=a[i]
    m=min(m,ai+bi-2)
print(m)


### FIXED CODE ###

n=int(input())
m=float("inf")
for i in range(1,1000001):
    if n%i==0:
        m=min(m,n//i+i-2)
print(m)
### BUGGY CODE ###

import math

N=int(input())
A=[0]*N
for i in range(N):
  A[i] = int(input())

S = sum(A)
maxA = max(A)
dp = [[0 for i in range(S+1+maxA-math.ceil(S/2))] for j in range(N+1)]
dp[0][S+1-math.ceil(S/2)-1]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = dp[i-1][j+A[i-1]]*2 + dp[i-1][j]
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0 for i in range(S+1+maxA-math.ceil(S/2))] for j in range(N+1)]
  dp2[0][S+1-math.ceil(S/2)-1]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = dp2[i-1][j+A[i-1]] + dp2[i-1][j]
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)