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

import numpy as np

s = input()

dp = np.zeros((100100,13))

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007

for i in range(len(s)):
	if s[i] == '?':
		for num in range(10):
			for j in range(13):
				dp[i+1][(j+num*ten)%13] += dp[i][j]
				dp[i+1][(j+num*ten)%13] %= mod
	else:
		num = int(s[i])
		for j in range(13):
			dp[i+1][(j+num*ten)%13] += dp[i][j]
			dp[i+1][(j+num*ten)%13] %= mod
	ten *= 10
	ten %= 13

print(int(dp[len(s)][5]%mod))

### FIXED CODE ###

from sys import stdin
s = stdin.readline()[:-1]

length = len(s)

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

s = list(reversed(s))

dp[0][0]=1
ten = 1
mod = 1000000007


for i in range(length):
	if s[i] == '?':
		for num in range(10):
			d = num*ten
			for j in range(13):
				k = (j+d)%13
				dp[i+1][k] += dp[i][j]
				dp[i+1][k] %= mod
	else:
		num = int(s[i])
		d = num*ten
		for j in range(13):
			k = (j+d)%13
			dp[i+1][k] += dp[i][j]
			dp[i+1][k] %= mod
	ten *= 10
	ten %= 13

print(int(dp[length][5]%mod))
### BUGGY CODE ###

import itertools

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
data = []
for i in range(0,m):
    a,b,c = map(int,input().split())
    data.append((a,b,c))
    data.append((b,a,c))

d = [[] for _ in range(0,R)]

def bellmanFord(start,num):
    g = [float("inf") for _ in range(0,n+1)]
    g[start] = 0
    for i in range(0,n):
        for j in range(0,m*2):
            a,b,c = data[j]
            if g[a] != float("inf") and g[b] > g[a] + c:
                g[b] = g[a] + c
    for i in range(0,R):
        d[num].append(g[r[i]])

for i in range(0,R):
    bellmanFord(r[i],i)
    # print(d[i])
ans = float("inf")
seq = itertools.permutations([i for i in range(0,R)])
for i in seq:
    dis = 0
    for j in range(0,len(i)-1):
        dis += d[i[j]][i[j+1]]
    if ans > dis:
        ans = dis
print(ans)

### FIXED CODE ###

import itertools

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
data = [[]for _ in range(0,n+1)]
d = [[] for _ in range(0,R)]

for i in range(0,m):
    a,b,c = map(int,input().split())
    data[a].append((b,c))
    data[b].append((a,c))

def dijkstra(start,num):
    g = [float("inf") for _ in range(0,n+1)]
    used = ["false" for _ in range(0,n+1)]
    g[start] = 0
    queue= []
    queue.append((start,data[start]))
    while queue:
        start,edge = queue.pop(0)
        for to,cost in edge:
            if g[to] > g[start] + cost:
                g[to] = g[start] + cost
                queue.append((to,data[to]))
    for i in range(0,R):
        d[num].append(g[r[i]])
    # print(g)
# dijkstra(1,0)

for i in range(0,R):
    dijkstra(r[i],i)
    # print(d[i])
ans = float("inf")
seq = itertools.permutations([i for i in range(0,R)])
for i in seq:
    dis = 0
    for j in range(0,len(i)-1):
        dis += d[i[j]][i[j+1]]
    if ans > dis:
        ans = dis
print(ans)
### BUGGY CODE ###

# 通過の種類は10の100乗 + 1 種類
# 10の(10の100乗)乗の桁数は10の100乗桁 (1グーゴル)
# 10の6乗 = 1000000 (100万)
# 通過の方が圧倒的に大きい

s = input()[::-1]  # 与えられた数を下の桁から見る
length = len(s)
dp = [[0]*2 for _ in range(length+1)]  # j=1を更新するとき、お釣りの部分を格納していることになる（支払った1枚の紙幣は次のタイムステップで更新される）
for i in range(length):
    # 今見ている桁に関して、ちょうど支払うとき
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+int(s[i])+1)

    # 今見ている桁に関して、1つ大きい桁の紙幣を1枚使って支払う
    if i != 0:
        # ここで格納される値はお釣りの部分と考えることができる
        dp[i+1][1] = min(dp[i][0]+10-int(s[i]), dp[i][1]+(10-1)-int(s[i]))
    else:
        dp[i+1][1] = dp[i][0]+10-int(s[i])  # お釣りの部分のみが格納されている

print(min(dp[length][0], dp[length][1]+1))


### FIXED CODE ###

# 通過の種類は10の100乗 + 1 種類
# 10の(10の100乗)乗の桁数は10の100乗桁 (1グーゴル)
# 10の6乗 = 1000000 (100万)
# 通過の方が圧倒的に大きい

s = input()[::-1]  # 与えられた数を下の桁から見る
length = len(s)
dp = [[0]*2 for _ in range(length+1)]  # j=1を更新するとき、お釣りの部分を格納していることになる（支払った1枚の紙幣は次のタイムステップで更新される）
for i in range(length):
    # 今見ている桁に関して、ちょうど支払うとき
    dp[i+1][0] = min(dp[i][0]+int(s[i]), dp[i][1]+int(s[i])+1)

    # 今見ている桁に関して、1つ大きい桁の紙幣を1枚使って支払う
    if i != 0:
        # ここで格納される値はお釣りの部分と考えることができる
        dp[i+1][1] = min(dp[i][0]+10-int(s[i]), dp[i][1]+(10-1)-int(s[i]))
    else:
        dp[i+1][1] = dp[i][0]+10-int(s[i])  # お釣りの部分のみが格納されている

print(min(dp[length][0], dp[length][1]+1))
### BUGGY CODE ###

from collections import defaultdict
import numpy as np

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x-1))

if any(x != 0 for l,x in Q[1]):
  print(0)
  exit(0)

dp = np.zeros((N,N), dtype='i8')
dp[0,0] = 3
memo = np.zeros(N, dtype='i8')
memo[0] = 6
s = 3

indices = {(0,0)}

for pk in range(1,N):
  k = pk+1
  dp[:pk,pk] = memo[:pk]
  memo[:pk] *= 2

  memo[pk] = 2*s%MOD
  s = 3*s%MOD
  subQ = Q[k]

  indices.update((i,pk) for i in range(pk))
  removes = []

  for i,j in indices:
    for l,x in subQ:
      if x != int(l<=i)+int(l<=j):
        c = dp[i,j]
        memo[i] -= c
        memo[j] -= c
        s -= c
        removes.append((i,j))
        break

  indices.difference_update(removes)

  memo[:pk] %= MOD
  s %= MOD

print(s)

### FIXED CODE ###

from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,(a,b) in enumerate(zip(x_sum,y_sum)):
    c = (a+b)%MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j)+1:
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)
### BUGGY CODE ###

##SPEED TEST##
n,ma,mb=map(int,input().split())
ab=[[[10**6]*401 for _ in range(401)] for _ in range(n+1)]
ab[0][0][0]=0

for p in range(1,n+1):
    a,b,c=map(int,input().split())
    for i in range(400):
        for j in range(400):
            ab[p][i][j]=min(ab[p][i][j],ab[p-1][i][j])
            if i+a<=400 and j+b<=400:
                ab[p][i+a][j+b]=min(ab[p][i+a][j+b],ab[p-1][i][j]+c)

ans=10**6-1
for i in range(401):
    for j in range(401):
        if i!=0 and j!=0:
            if i*mb==j*ma:
                ans=min(ans,ab[n][i][j])

if ans==10**6-1:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n,ma,mb=map(int,input().split())
ab=[[[10**6]*401 for _ in range(401)] for _ in range(n+1)]
ab[0][0][0]=0

for p in range(1,n+1):
    a,b,c=map(int,input().split())
    for i in range(400):
        for j in range(400):
            ab[p][i][j]=min(ab[p][i][j],ab[p-1][i][j])
            if i+a<=400 and j+b<=400:
                ab[p][i+a][j+b]=min(ab[p][i+a][j+b],ab[p-1][i][j]+c)

ans=10**6-1
for i in range(401):
    for j in range(401):
        if i!=0 and j!=0:
            if i*mb==j*ma:
                ans=min(ans,ab[n][i][j])

if ans==10**6-1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
s = []
for i in range(max(S) + 1):
    if i in S:
        s.append(i)
c = 0
for i in T:
    if (i in s):
        c += 1
    
print(c)


### FIXED CODE ###

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
c = 0
for i in range(q):
    l = 0
    r = n
    t = T[i]
    while r-l > 1:
        m = (r + l)//2
        if (S[m] > t):
            r = m
        else:
            l = m
    if (S[l] == T[i]):
        c += 1
print(c)
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 100
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = sorted(LI())
s = set()
B = [0] * (10 ** 6 + 1)
for a in A:
    i = 2
    if a in s:
        continue
    while a * i <= 10 ** 6:
        B[a * i] = 1
        i += 1

cnt = Counter(A)
ans = 0
for a in A:
    if B[a] == 0 and cnt[a] == 1:
        ans += 1

print(ans)





### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = sorted(LI())
ans = 0
cnt = Counter(A)
m = max(A) + 1
B = [0] * (10 ** 6 + 1)
for a in A:
    if B[a] == 0 and cnt[a] == 1:
        ans += 1
    for i in range(a * 2, m, a):
        B[i] = 1


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

# https://atcoder.jp/contests/abc094/tasks/arc095_a
# C - Many Medians

n = int(input().split()[0])
x_list = list(map(int, input().split()))
sorted_x_list = sorted(x_list)
mean_index = int((n + 1)/ 2) - 1
mean_list = []

for i, x in enumerate(x_list):
    if i < n - 1:
        w_list = sorted(x_list[:i] + x_list[i+1:])
    else:
        w_list = sorted(x_list[:i] + x_list[i+1:])

    mean_value = w_list[mean_index]
    mean_list.append(str(mean_value))

ans = '\n'.join(mean_list)
print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/abc094/tasks/arc095_a
# C - Many Medians
import copy

n = int(input().split()[0])
x_list = list(map(int, input().split()))
sorted_x_list = sorted(x_list)
mean_index = int((n + 1)/ 2) - 1
mean_list = []

a = sorted_x_list[mean_index]
b = sorted_x_list[mean_index + 1]
for x in x_list:
    if x <= a:
        mean_list.append(str(b))
    else:
        mean_list.append(str(a))

ans = '\n'.join(mean_list)
print(ans)
### BUGGY CODE ###

def solve(n,a,b):
    dp=[0]*(n+1)
    for w in range(n+1): dp[w]=max(w,dp[w-a[0]]+b[0]if w-a[0]>=0 else w,dp[w-a[1]]+b[1]if w-a[1]>=0 else w,dp[w-a[2]]+b[2]if w-a[2]>=0 else w)
    return dp[-1]
N,A,B=int(input()),list(map(int, input().split())),list(map(int, input().split()))
print(solve(solve(N,A,B),B,A))

### FIXED CODE ###

def solve(n,a,b):
    dp=[0]*(n+1)
    for w in range(n+1): dp[w]=max(w,dp[w-a[0]]+b[0]if w-a[0]>=0 else w,dp[w-a[1]]+b[1]if w-a[1]>=0 else w,dp[w-a[2]]+b[2]if w-a[2]>=0 else w)
    return dp[-1]
N,A,B=int(input()),list(map(int, input().split())),list(map(int, input().split()))
print(solve(solve(N,A,B),B,A))
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = {i + 1:[] for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
com = 1
check_list = [1]
count = {i + 1:0 for i in range(n)}
while check_list:
    check = check_list.pop(0)
    next_check = graph[check]
    for i in range(len(next_check)):
        count[next_check[i]] += i
        check_list.append(next_check[i])
        graph[next_check[i]].remove(check)
    set_1 = set(graph[1])
    if check == 1:
        com *= k
    elif check in set_1:
        com *= k - 1 - count[check]
        com %= mod
    else:
        com *= k - 2 - count[check]
        com %= mod
print(com)

### FIXED CODE ###

import collections

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag[1] = True
queue = collections.deque([1])
ans = k
while queue:
    test = queue.popleft()
    temp = [flag[graph[test][i]] for i in range(len(graph[test]))].count(True)
    num = 0
    for i in range(len(graph[test])):
        if flag[graph[test][i]] == True:
            continue
        ans *= (k - temp - num - 1)
        ans %= mod
        num += 1
        queue.append(graph[test][i])
        flag[graph[test][i]] = True
print(ans)
### BUGGY CODE ###

from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()

### FIXED CODE ###

from sys import stdin, maxsize

def main():
    input = stdin.readline

    h, n = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(n)]
    dp = [maxsize] * (h + 1)
    dp[0] = 0
    for i in range(h + 1):
        for x, y in a:
            if i + x < h and dp[i + x] > dp[i] + y:
                dp[i + x] = dp[i] + y
            elif i + x >= h and dp[h] > dp[i] + y:
                dp[h] = dp[i] + y
    print(dp[h])
main()
### BUGGY CODE ###

n, K = map(int,input().split())
A = list(map(int,input().split()))
b = [0 for _ in range(n+1)]

for _ in range(K):
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    for i in range(n):
        b[i+1] += b[i]
    A = b[:-1]
    b = [0 for _ in range(n+1)]
    if sum(A) == n*n:
        break
    
print(*A)

### FIXED CODE ###

n, K = map(int,input().split())
A = list(map(int,input().split()))

for _ in range(K):
    b = [0 for _ in range(n+1)]
    for i,a in enumerate(A):
        b[max(0, i-a)] += 1
        b[min(n, i+a+1)] -= 1

    for i in range(n):
        b[i+1] += b[i]

    A = b[:-1]
    if all(a == n for a in A):
        break
print(*A)
### BUGGY CODE ###

from sys import stdin

S = stdin.readline().rstrip()

beforeS = S

while(True):
    after_S = S.replace("01", "").replace("10", "")
    if len(after_S) != len(S):
        S = after_S
    else:
        break

print(len(beforeS) - len(S))

### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()

stack = []
count = 0

for s in S:
    # スタックが空なら
    if not stack:
        stack.append(s)
    # スタックの一番上がsでなければ
    elif stack[-1] != s:
        stack.pop()
        count += 2
    else:
        stack.append(s)

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

islands = []
bridges = []

N, M = map(int, input().split())
# N, M = 10, 5
# islands = [
#     {'a': 1, 'b': 10},
#     {'a': 2, 'b': 5},
#     {'a': 1, 'b': 9},
#     {'a': 2, 'b': 4},
#     {'a': 1, 'b': 2},
# ]

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: (x['b'], x['a']))
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    b = [j for j in b if j < i['b']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))


### FIXED CODE ###

islands = []
bridges = []

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

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: x['b'])
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import math
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

k = I()

result = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        frc = fractions.gcd(i,j)
        for l in range(1, k+1):
            result += fractions.gcd(frc, l)

print(result)


### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import math
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

k = I()

result = 0

gcdList = {}

frc = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        t = (i,j)
        if t in gcdList:
            frc = gcdList[t]
        else:
            frc = fractions.gcd(i,j)
            gcdList[t] = frc
            
        for l in range(1, k+1):
            t2 = (gcdList[(i,j)],l)
            
            if t2 in gcdList:
                frc = gcdList[t2]
            else:
                frc = fractions.gcd(gcdList[(i,j)],l)
                gcdList[t2] = frc
            
            result += frc

print(result)
### BUGGY CODE ###



n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(-1 * 10**9, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	odd = [0]
	even = [0]
	for i in range(n // 2):
		odd.append(odd[-1] + a[2*i])
		even.append(even[-1] + a[2*i+1])
	if n % 2 == 1:
		odd.append(odd[-1] + a[-1])

	answer = -1 * 10**9 * n
	if n % 2 == 0:
		for i in range(n // 2 + 1):
			answer = max(answer, odd[i] - even[i] + even[-1])
	else:
		for i in range(n // 2 + 2):
			if i < n // 2 + 1:
				for j in range(i+1):
					answer = max(answer, odd[j] - even[j] + even[i] - odd[i+1] + odd[-1])
			else:
				for j in range(i):
					answer = max(answer, odd[j] - even[j] + even[-1])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)


### FIXED CODE ###



n = 0
a = []

def format_input(filename = None):
	global n
	global a
	if filename == None:
		n = int(input())
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(2, 2 * 10**5)
		a = [rng(-1 * 10**9, 10**9) for i in range(n)]
		print(n)
		print(' '.join(list(map(str, a))))

def get_answer():
	odd = [0]
	even = [0]
	for i in range(n // 2):
		odd.append(odd[-1] + a[2*i])
		even.append(even[-1] + a[2*i+1])
	if n % 2 == 1:
		odd.append(odd[-1] + a[-1])

	answer = -1 * 10**9 * n
	if n % 2 == 0:
		for i in range(n // 2 + 1):
			answer = max(answer, odd[i] - even[i] + even[-1])
	else:
		even_range = [even[0] - odd[1]]
		for i in range(n // 2):
			add = a[2*i+1] - a[2*i+2]
			min = - a[2*i] + add
			even_range.append(max(even_range[-1] + add, min))
		answer = odd[-1] + max(even_range)
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
*a, = map(int, input().split())

s = [0]*N
s[0] = a[0]
for i in range(1, N):
    s[i] += s[i-1]+a[i]
s = [0]+s

dp = [[0]*(N+1) for _ in range(N+1)]


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    n = float('inf')
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
*a, = map(int, input().split())

s = [0]*N
s[0] = a[0]
for i in range(1, N):
    s[i] += s[i-1]+a[i]
s = [0]+s

dp = [[0]*(N+1) for _ in range(N+1)]


def solve(l, r):
    if l == r:
        return 0
    if dp[l][r] > 0:
        return dp[l][r]

    n = float('inf')
    m = s[r+1]-s[l]
    for i in range(l, r):
        n = min([n, solve(l, i)+solve(i+1, r)+m])
    dp[l][r] = n
    return n


print(solve(0, N-1))
### BUGGY CODE ###

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

l = {}
ans = []
for e in a:
    l[e] = l[e] + 1 if l.get(e) else 1

for _ in range(q):
    b, c = map(int, input().split())
    if b in l:
        l[c] = l[c] + l[b] if l.get(c) else l[b]
        del l[b]
    sum = 0
    for k, v in l.items():
        sum += k * v
    ans.append(sum)

for sum in ans:
    print(sum)

### FIXED CODE ###

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

l = [0] * 100001
for i in a:
    l[i] += 1

s = sum(a)

for _ in range(q):
    b, c = map(int, input().split())
    s += (c - b) * l[b]
    l[c] += l[b]
    l[b] = 0
    print(s)
### BUGGY CODE ###

N, W = map(int, input().split())
a = [list(map(int, list(input().split()))) for i in range(N)]
dp = [[0]*(W+1) for i in range(N)]  # initialize dp

for i in range(N):
    for k in range(W+1):
        if i == 0:
            if a[0][0] <= k and k <= W:
                dp[0][k] = a[0][1]
        else:
            if a[i][0] <= k and k <= W:
                dp[i][k] = max(dp[i-1][k], dp[i-1][k-a[i][0]] + a[i][1])
            else:
                dp[i][k] = dp[i-1][k]
print(dp[N-1][W])

### FIXED CODE ###

N, W = map(int, input().split())
a = [list(map(int, list(input().split()))) for i in range(N)]
dp = [[0]*(W+1) for i in range(N)]  # initialize dp

for i in range(N):
    for k in range(W+1):
        if i == 0:
            if a[0][0] <= k and k <= W:
                dp[0][k] = a[0][1]
        else:
            if a[i][0] <= k and k <= W:
                dp[i][k] = max(dp[i-1][k], dp[i-1][k-a[i][0]] + a[i][1])
            else:
                dp[i][k] = dp[i-1][k]
print(dp[N-1][W])
### BUGGY CODE ###

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

A_set = list(set(A))
len_A_set = len(A_set)

A_count =[]
for i in range(len_A_set):
    A_count.append(A.count(A_set[i]))

ans=0
for i in range(len_A_set-K):
    ans += min(A_count)
    A_count.pop(A_count.index(min(A_count)))

print(ans)


### FIXED CODE ###

from collections import Counter
N, K=list(map(int, input().split()))
A=list(map(int, input().split()))

X=Counter(A)
X2 = sorted(X.items(), key=lambda x:x[1])
ans=0
for i in range(len(X2)-K):
    ans+=X2[i][1]
print(ans)