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

n, p = map(int, input().split())
dic = {}

for i in range(2,p+1):
    while p%i==0:
        if i not in dic.keys():
            dic[i] = 0
        p = p// i
        dic[i] += 1
        
    if p==1:
        break
        
out=1
for i in dic.keys():
    if dic[i] >=n:
        out *= i**(dic[i]//n)

print(out)

### FIXED CODE ###

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

if n==1:
    print(p)
else:
    out=1
    tm = int(pow(p, 1/n))
    for i in range(2,tm+1):
        while p%(i**n)==0:
            p = p//(i**n)
            out *= i
        if p < i**n:
            break
    print(out)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    for i in range(N):
        if not used[i]:
            dfs(i)
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)

graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)

label,group = scc(N,graph,graph)
print(label)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        for _ in range(num): return []
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list,zip(*read_all))

#################

#強連結成分分解
#label：グループ数
#group[i]：i個目のノードが所属するグループ
def scc(N, G, RG):
    used = [False]*N
    group = [None]*N
    order = []
    def dfs(S):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in G[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            order.append(v1)
    for i in range(N):
        if not used[i]:
            dfs([i])
    def rdfs(S,col):
        used[S[0]] = True
        while S:
            v1 = S.pop()
            for v1_to in RG[v1]:
                if not used[v1_to]:
                    used[v1_to] = True
                    S.append(v1_to)
            group[v1] = col
    used = [False]*N
    label = 0
    for s in order:
        if not used[s]:
            rdfs([s], label)
            label += 1
    return label, group

N,M = II()
X,Y,Z = Line(M,3)

graph = [[] for _ in range(N)]
for i in range(M):
    graph[X[i]-1].append(Y[i]-1)
    graph[Y[i]-1].append(X[i]-1)

label,group = scc(N,graph,graph)
print(label)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
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])
count=0
for edge in range(m):
  flag=False
  for j in range(n):
    for k in range(n):
      if d[j][a[edge]]+c[edge]==d[j][b[edge]]:
        flag=True
        break
    if flag:
      break
  else:
    count+=1
print(count)


### FIXED CODE ###

import sys
from copy import deepcopy
input = sys.stdin.readline
n,m=map(int,input().split())
d=[[100000]*n for _ in range(n)]
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
  a0,b0,c0=map(int,input().split())
  a[i]=a0-1
  b[i]=b0-1
  c[i]=c0
  d[a0-1][b0-1]=c0
  d[b0-1][a0-1]=c0
for i in range(n):
  d[i][i]=0
d2=deepcopy(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])
count=0
for i in range(n):
  for j in range(i):
    if d2[i][j] != 100000 and d[i][j]!=d2[i][j]:
      count+=1
print(count)
### BUGGY CODE ###

import numpy as np

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

result = 0

for i in range(n):
    result += np.min([a[i]+a[i+1], b[i]])
    a[i+1] = np.min([np.max([0, a[i]+a[i+1] - b[i]]), a[i+1]])
print(result)

### FIXED CODE ###

import numpy as np

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


result = 0

for i in range(n):
    if a[i] <= b[i]:
        result += a[i]
        if a[i]+a[i+1] < b[i]:
            result += a[i+1]
            a[i+1] = 0
        else:
            diff = a[i]+a[i+1] - b[i]
            result += (a[i+1] - diff)
            a[i+1] = diff
    else:
        result += b[i]
        
print(result)
### BUGGY CODE ###

n,k = map(int,input().split())
lamps = list(map(int,input().split()))
for ki in range(k):
    lamplog = [0]*(n+1)
    for i in range(n):
        lamplog[max(0,i-lamps[i])  ] += 1   #先端を出す
        lamplog[min(i+lamps[i]+1,n)] -= 1   #末尾を出す
    # print(lamplog)
    for i in range(n):                      #累積和を計算
        lamplog[i+1] += lamplog[i]
    # print(lamplog)
    lamplog.pop()
    if(lamplog == lamps):                   #１つ前の結果と今回の結果が同じだったら。
        break
    lamps = lamplog                         #今回の結果を記録

ans = ""
for i in range(len(lamplog)):
    ans += str(lamplog[i]) +" "
print(ans.rstrip())


### FIXED CODE ###

from numba import jit
@jit
def main():
    n,k = map(int,input().split())
    lamps = list(map(int,input().split()))
    for ki in range(k):
        lamplog = [0]*(n+1)
        for i in range(n):
            lamplog[max(0,i-lamps[i])  ] += 1   #先端を出す
            lamplog[min(i+lamps[i]+1,n)] -= 1   #末尾を出す
        # print(lamplog)
        for i in range(n):                      #累積和を計算
            lamplog[i+1] += lamplog[i]
        # print(lamplog)
        lamplog.pop()
        if(lamplog == lamps):                   #１つ前の結果と今回の結果が同じだったら。
            break
        lamps = lamplog                         #今回の結果を記録
    return lamplog

lamplog = main()
ans = ""
for i in range(len(lamplog)):
    ans += str(lamplog[i]) +" "
print(ans.rstrip())
### BUGGY CODE ###

from itertools import combinations

N = int(input())

line = input()
target_itr = (list(combinations(range(N), 3)))


def ok_list(target_itr):
    for target in target_itr:
        if (target[1] - target[0]) != (target[2] - target[1]):
            yield target[0], target[1], target[2]


def itr_line(line, target_itr):
    for combination in target_itr:
        i = line[combination[0]]
        j = line[combination[1]]
        k = line[combination[2]]

        if i != j and i != k and j != k:
            yield i, j, k


result = list(itr_line(line, ok_list(target_itr)))
print(len(result))


### FIXED CODE ###

from itertools import groupby
from statistics import median
from sys import exit

N = int(input())

line = ([(index, v) for index, v in enumerate(input())])


def types(line): return line[1]
def index(line): return line[0]


gp = groupby(sorted(line, key=types), types)

d = {}

for k, v in gp:
    indexes = set([i for i, value in v])
    d[k] = indexes

if 'R' not in d or 'G' not in d or 'B' not in d:
    print(0)
    exit()

delete = 0


for differ in range(1, N):
    for start in range(N):
        if start + differ*2 > N - 1:
            break

        i = line[start]
        j = line[start + differ]
        k = line[start + differ*2]

        if len({i[1], j[1], k[1]}) != 3:
            continue

        upper = max(i[0], j[0], k[0])
        lower = min(i[0], j[0], k[0])
        median_num = median([i[0], j[0], k[0]])
        if upper - median_num == median_num - lower:
            delete += 1

print(len(d['R']) * len(d['G']) * len(d['B']) - delete)
### BUGGY CODE ###

# おなじみ 1/w = ...の形からもっていくとw = ..が導出できた

N = int(input())
for n in range(1, 3501):
    for h in range(1, 3501):
        t = 4 * n * h - N * (h + n)
        if t == 0 or t < 0:
            continue
        w = (N * n * h) / t
        if int(w) == w:
            w = int(w)
            print(h, n, w)
            exit()


### FIXED CODE ###

# おなじみ 1/w = ...の形からもっていくとw = ..が導出できた

N = int(input())
for n in range(1, 3501):
    for h in range(1, 3501):
        t = 4 * n * h - N * (h + n)
        if t == 0 or t < 0:
            continue
        w = (N * n * h) / t
        if int(w) == w:
            w = int(w)
            print(h, n, w)
            exit()
### BUGGY CODE ###

def score_search(sc, idx):
    if idx == len(f):
        if sc % 10 == 0:
            sc = 0
        return sc

    sc_lst = [0, 0]
    sc_lst[0] = sc + score_search(0, idx+1)
    if sc_lst[0] % 10 == 0:
        sc_lst[0] = 0
    sc += s[f[idx]]
    sc_lst[1] = sc + score_search(0, idx+1)
    if sc_lst[1] % 10 == 0:
        sc_lst[1] = 0
    return max(sc_lst)


n = int(input())
s = [int(input()) for i in range(n)]
f, score = [], 0

for i in range(len(s)):
    if s[i] % 10:
        f.append(i)
    else:
        score += s[i]


best_score = score + score_search(0, 0)
if best_score % 10 == 0:
    best_score = 0

print(best_score)


### FIXED CODE ###

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

    sum_max = sum(s)

    if sum_max % 10 == 0:
        min_p = 101
        for i in s:
            if i % 10 != 0 and i < min_p:
                min_p = i

        if min_p == 101:
            sum_max = 0
        else:
            sum_max -= min_p

    print(sum_max)


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

import math as mt
import itertools as iters

K = int(input())
A = 0
for a,b,c in iters.product(range(1,K+1),repeat=3):
    A += mt.gcd(a,mt.gcd(b,c))
print(A)

### FIXED CODE ###

import math as mt
import itertools as iters

K = int(input())
A = 0
for a,b,c in iters.product(range(1,K+1),repeat=3):
    A += mt.gcd(a,mt.gcd(b,c))
print(A)
### BUGGY CODE ###

#!/usr/bin/env python

import sys

s= sys.stdin.readline().strip()
n= len(s)
#
c= 0
#
while True:
    i = s.find("ABC")
    if i<0: break
    a = 1
    for j in range(i-1,-1,-1):
        if s[j]=="A": a+=1
        else: break
    #
    bc= 1
    for j in range(i+3,n,2):
        if s[j:j+2]=="BC": bc+=1
        else: break
    #
    j= i+2*bc
    s= ("A"*a) + s[j+1:]
    n-= j - a
    c+= a*bc
print( c )


### FIXED CODE ###

#!/usr/bin/env python

import sys
import re

s= sys.stdin.readline().strip()
s= s.replace("BC","D")
s= re.sub("[BC]+"," ",s).split()

t= 0
for seg in s:
    a= 0
    for c in seg:
        if c=="A": a+=1
        elif c=="D": t+= a
#
print( t )
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# Factoring by trial split
def getPrimeList(n):
  l=[]
  t=int(math.sqrt(n))+1
  
  for a in range(2,t):
    while n%a==0:
      n//=a
      l.append(a)
  
  if n!=1:
    l.append(n)
  
  return l

def main():
  n=I()

  a=getPrimeList(n)

  # l=[]
  # b=len(bin(1<<len(a)))-3
  # for i in range(1<<len(a)):
  #   l.append(str(bin(i))[2:].zfill(b))
  
  # ans=inf
  # for x in l:
  #   _a=_b=1
  #   for i,y in enumerate(list(x)):
  #     if y=='0':
  #       _a*=a[i]
  #     else:
  #       _b*=a[i]
  #   ans=min(ans,_a+_b-2)

  # return ans

  ans=inf
  b=len(a)
  for i in range(2**b):
    _a=_b=1
    for j in range(b):
      if ((i >> j) & 1):
        _a*=a[j]
      else:
        _b*=a[j]
    ans=min(ans,_a+_b-2)
  return ans

# main()
print(main())


### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  ans=inf
  for x in range(1,int(math.sqrt(n))+1):
    if n%x==0:
      ans=min(ans,x+n//x-2)
  return ans

# main()
print(main())
### BUGGY CODE ###

def solve(a,M):
	for x,y in xy:
		if x in a and (y not in a or a.index(x) > a.index(y)):
			break
	else:
		if len(a) == m: return a
		return max([solve([M[i]] + a,M[:i]+M[i+1:]) for i in range(len(M))])

m = input()
xy = [map(int,raw_input().split()) for i in range(input())]
M = range(m)
ans = solve([],range(1,m+1))
for i in ans: print i

### FIXED CODE ###

def solve(a):
	for i in M-set(a):
		if any(x == i and y not in a for x,y in xy): continue
		r = solve([i]+a)
		if r: return r
	return a
m = input()
M = set(range(1,m+1))
xy = [map(int,raw_input().split()) for i in range(input())]
for i in solve([]): print i
### BUGGY CODE ###

import math
from functools import reduce

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

K = int(input())
output = 0
for i1 in range(1,K+1):
    for i2 in range(1,K+1):
        for i3 in range(1,K+1):
            output += gcd(i1,i2,i3)
print(output)

### FIXED CODE ###

import math
from functools import reduce

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

K = int(input())
output = 0
for i1 in range(1,K+1):
    for i2 in range(1,K+1):
        for i3 in range(1,K+1):
            output += gcd(i1,i2,i3)
print(output)
### BUGGY CODE ###

#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [0] * N #最短距離を記録しておくリスト
# prev = [-1] * N
def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        count += 1
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                # prev[e[1]] = e[0]
        if not update: #更新が終わったとき
            return True
        if count == N - 1: #永遠に更新が起きているとき
            tmp = d[N -1]
        if count == 5 * N:
            if d[N - 1] == tmp:
                return True #N-1の値が更新されていないとき
            else:
                return False #N + 2回目でもN - 1の値が小さくなっている-->得点が無限に大きくなる

#呼び出しスタート地点を入れる
if not shortest_path(1):
    print (-1)
    # print (d)
    exit()
# print (d)

print (max(0, -d[N - 1]))

### FIXED CODE ###

#単一始点最短経路問題
#負の辺があっても動作する

#最短経路を求める
#計算量O(N * M)

INF = 10 ** 15
#入力
# N = int(input()) #頂点の数
# M = int(input()) #辺の数
N, M, P = map(int, input().split())

# 入力は1-index
# 内部で0-indexにして処理
G = []
for _ in range(M): #M個の辺の情報を受け取る
    l, r, s = map(int, input().split()) #lからrへ重みsの辺が存在
    G += [[l-1, r-1, -(s-P)]] #有向グラフのときはここだけ
    # G += [[r-1, l-1, s]] #無向グラフのときはこの行も必要


#メイン文
d = [0] * N #最短距離を記録しておくリスト
# prev = [-1] * N
def shortest_path(s): #S番目の頂点から各頂点への最短距離を求める
    s -= 1
    for i in range(N):
        d[i] = INF
    d[s] = 0
    count = 0
    while True:
        count += 1
        update = False
        for i in range(M): #無向グラフのときは辺は実質的には2倍
            e = G[i]
            if d[e[0]] != INF and d[e[1]] > d[e[0]] + e[2]:
                d[e[1]] = d[e[0]] + e[2]
                update = True
                # prev[e[1]] = e[0]
        if not update: #更新が終わったとき
            return True
        if count == N - 1: #永遠に更新が起きているとき
            tmp = d[N -1]
        if count == 2 * N:
            if d[N - 1] == tmp:
                return True #N-1の値が更新されていないとき
            else:
                return False #N + 2回目でもN - 1の値が小さくなっている-->得点が無限に大きくなる

#呼び出しスタート地点を入れる
if not shortest_path(1):
    print (-1)
    # print (d)
    exit()
# print (d)

print (max(0, -d[N - 1]))
### BUGGY CODE ###

import itertools
n = int(input())
s = list(map(int, [input() for _ in range(n)]))
ans = []
for i in range(1, n + 1):
  for j in itertools.combinations(s, i):
    sum_ = sum(j)
    if sum_ % 10 == 0:
      sum_ = 0
    ans.append(sum_)
print(max(ans))

### FIXED CODE ###

n = int(input())
s = list(map(int, [input() for _ in range(n)]))
if sum(s) % 10 == 0:
  while sum(s) % 10 == 0 and len(s) > 0:
    s = sorted(s)
    i = 0
    while s[i] % 10 == 0 and i + 1 < len(s):
      i += 1
    del s[i]
  print(sum(s))
else:
  print(sum(s))
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
l = [list(map(int, input().split())) for _ in range(m)]
for i in range(m):
    print(s[l[i][0]-1:l[i][1]].count("AC"))

### FIXED CODE ###

n, m = map(int, input().split())
s = input()
t = [0] * (n+1)
for i in range(n):
    if s[i:i + 2] == "AC":
        t[i + 1] = t[i] + 1
    else:
        t[i + 1] = t[i]
for i in range(m):
    a, b = map(int, input().split())
    print(t[b-1] - t[a-1])
### BUGGY CODE ###

import fractions
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
gcds = []
for N in range(n):
    b = a.copy()
    b.remove(b[N])
    gcds.append(reduce(fractions.gcd, b))
print(max(gcds))

### FIXED CODE ###


import fractions
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
gcds = 0
r = [0]
l = [0]
for N in range(n):
	r.append(fractions.gcd(r[N],a[N]))
	l.append(fractions.gcd(l[N],a[n - N - 1]))
for i in range(n):
	gcds = max(gcds,(fractions.gcd(r[i],l[n - i - 1])))
print(gcds)
### BUGGY CODE ###

s=input()
q=int(input())
quary=[]
for i in range(q):
    temp=list(input().split())
    quary.append(temp)

for i in range(q):
    if quary[i][0]=='1':
        s=s[::-1]
    else:
        if quary[i][1]=='1':
            s=quary[i][2]+s
        else:
            s=s+quary[i][2]
print(s)

### FIXED CODE ###

s=input()
q=int(input())
quary=[]
for i in range(q):
    temp=list(input().split())
    quary.append(temp)
switch=False
first=''
last=''
for i in range(q):
    if quary[i][0]=='1':
        if switch:
            switch=False
        else:
            switch=True

    else:
        if quary[i][1]=='1':
            if switch:
                last+=quary[i][2]
            else:
                first+=quary[i][2]
        else:
            if switch:
                first+=quary[i][2]
            else:
                last+=quary[i][2]
s=first[::-1]+s+last
if switch:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

from collections import OrderedDict
n, q = [int(el) for el in input().split(' ')]
data = OrderedDict({i:0 for i in range(n,0,-1)})
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a] += v
    result = OrderedDict(sorted(data.items(), key=lambda t: t[1], reverse=True))
    print(*result.popitem(False))

### FIXED CODE ###

n, q = [int(el) for el in input().split(' ')]
data = [0] * n
result, index = 0, 1
for _ in range(q):
    a, v = [int(el) for el in input().split(' ')]
    data[a-1] += v
    if v > 0:
        if result < data[a-1]:
            result, index = data[a-1], a
        elif result == data[a-1]:
            index = min(index, a)
    else:
        if index == a:
            result = max(data)
            index = data.index(result) + 1
    print(index, result)
### BUGGY CODE ###

S = input()
N = len(S)
T = [0] * (N+1)
cnt = {i:0 for i in range(2019)}
cnt[0] = 1
#T[i]: i+1文字目以降を数とみなしたときの数
for i in range(N-1, -1, -1):
    T[i] = (T[i+1] + int(S[i]) * 10 ** (N- i -1)) % 2019
    cnt[T[i]] += 1

ans = 0
for i in range(2019):
    m = cnt[i]
    ans += m * (m-1) // 2
print(ans)


### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

n = int(input())

divisors = [0 for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(i, n+1, i):
        divisors[j] += 1
#print(divisors)

ans = 0
for k in range(n+1):
    ans += (k * divisors[k])

print(ans)


### FIXED CODE ###

import numpy as np
from numba import jit

@jit
def solve():
    
    n = int(input())
    
    divisors = np.zeros(n+1, np.int64)
    
    for i in range(1, n+1):
        for j in range(i, n+1, i):
            divisors[j] += 1
    #print(divisors)
    
    ans = 0
    for k in range(n+1):
        ans += (k * divisors[k])
    
    print(ans)

solve()
### BUGGY CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        p2m = p2 % (n1 - 1)
        Xim = Xms - p2m if Xms - p2m >= 0 else ((n1 - 1) + (Xms - p2m))
    else:
        p2m = p2 % (n1 + 1)
        Xim = Xml + p2m if Xml + p2m < (n1 + 1) else (Xml + p2m - (n1 + 1))

    cnt += 1
    while Xim > 0:
        Xim % bin(Xim).count("1")
        cnt += 1
    print(cnt)



### FIXED CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)
### BUGGY CODE ###

import numpy as np
import collections
N, K = map(int, raw_input().split())
P_list = list()
for i in range(N):
    P_list.append(raw_input()[0])
    C_list = collections.Counter(P_list).values()

# clean
C_vec = np.array(C_list)
C_vec.sort()
C_vec = C_vec[::-1]

res = 0
while True:
    if len(C_list) >= K:
        d = C_vec[K-1]
        C_vec[0:K] -= d
        res += d
        C_vec = C_vec[C_vec > 0]
        C_vec.sort()
        C_vec = C_vec[::-1]
    else:
        break
print res

### FIXED CODE ###

import numpy as np
C_vec = np.zeros(26)
N, K = map(int, raw_input().split())

for i in range(N):
    C_vec[ord((raw_input()[0])) - ord('A')] += 1


while True:
    m = int(C_vec.sum() / K)
    C_vec = np.minimum(C_vec, m)
    m_next = int(C_vec.sum() / K)
    if m_next == m:
        break
    else:
        m = m_next

print m