CodeEff/ECCO huggingface dataset:
# Original solution
#!/usr/bin/env python3
from sys import stdin


def solve(tc):
    s = stdin.readline().strip()
    k = int(stdin.readline().strip())

    n = len(s)
    li = [list() for i in range(26)]
    for i in range(n):
        li[ord(s[i])-ord('a')].append(i)
    
    p = 0
    while len(li[p])==0:
        p += 1
    
    ans = set()
    while len(ans)<k and p<26:
        for i in range(n):
            for j in range(len(li[p])):
                b = li[p][j]
                e = min(n, li[p][j] + i + 1)
                ans.add(s[b:e])
        p += 1
    lans = list(ans)
    lans.sort()
    print((lans[k-1]))
    pass


LOCAL_TEST = not __debug__
if LOCAL_TEST:
    infile = __file__.split('.')[0] + "-test.in"
    stdin = open(infile, 'r')

tcs = (int(stdin.readline().strip()) if LOCAL_TEST else 1)
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1

# Optimized solution
#!/usr/bin/env python3
from sys import stdin


def solve(tc):
    s = stdin.readline().strip()
    k = int(stdin.readline().strip())

    n = len(s)
    li = [list() for i in range(26)]
    for i in range(n):
        li[ord(s[i])-ord('a')].append(i)
    
    p = 0
    while len(li[p])==0:
        p += 1
    
    ans = set()
    while len(ans)<k and p<26:
        for i in range(k):
            for j in range(len(li[p])):
                b = li[p][j]
                e = min(n, li[p][j] + i + 1)
                ans.add(s[b:e])
        p += 1
    lans = list(ans)
    lans.sort()
    print((lans[k-1]))
    # print(lans[k-1])
    pass


LOCAL_TEST = not __debug__
if LOCAL_TEST:
    infile = __file__.split('.')[0] + "-test.in"
    stdin = open(infile, 'r')

tcs = (int(stdin.readline().strip()) if LOCAL_TEST else 1)
tc = 1
while tc <= tcs:
    solve(tc)
    tc += 1
# Original solution
import sys

def solve():
    input = sys.stdin.readline
    s = input().strip("\n")
    K = int(eval(input()))
    substr = set()
    N = len(s)
    for i in range(N):
        for j in range(i+1, N + 1):
            substr |= {s[i:j]}
    sl = list(substr)
    sl.sort()
    print((sl[K-1]))

    return 0

if __name__ == "__main__":
    solve()

# Optimized solution
import sys

def solve():
    input = sys.stdin.readline
    s = input().strip("\n")
    K = int(eval(input()))
    substr = set()
    N = len(s)
    for i in range(N):
        for j in range(1, min(6, N - i + 1)):
            substr |= {s[i:i+j]}
    sl = list(substr)
    sl.sort()
    print((sl[K-1]))

    return 0

if __name__ == "__main__":
    solve()
# Original solution
s = input().strip()
K = int(eval(input()))
C = {}
for i in range(len(s)):
    if s[i] not in C:
        C[s[i]] = []
    C[s[i]].append(i)
if len(C)==1:
    a = s[0]
    print((a*K))
else:
    A = []
    for a in C:
        for i in C[a]:
            for j in range(i+1,len(s)+1):
                A.append(s[i:j])
    A = sorted(list(set(A)))
    print((A[K-1]))

# Optimized solution
s = input().strip()
K = int(eval(input()))
C = {}
for i in range(len(s)):
    if s[i] not in C:
        C[s[i]] = []
    C[s[i]].append(i)
D = {}
for a in C:
    for i in C[a]:
        for j in range(i+1,len(s)+1):
            if s[i:j] not in D:
                D[s[i:j]] = 0
            D[s[i:j]] += 1
D = sorted(list(D.keys()))
print((D[K-1]))
# Original solution
def all_index(s, c):
    ins = []
    for i in range(len(s)):
        if s[i] == c:
            ins.append(i)

    return ins


s = input().strip()
k = int(eval(input()))

ss = set()
alphabets = sorted(list(set(s)))
for c in alphabets:
    ins = all_index(s, c)
    for i in ins:
        for j in range(i, len(s)):
            ss.add(s[i:j+1])

    if len(ss) >= k:
        break

print((sorted(list(ss))[k-1]))

# Optimized solution
def all_index(s, c):
    ins = []
    for i in range(len(s)):
        if s[i] == c:
            ins.append(i)

    return ins


s = input().strip()
k = int(eval(input()))

ss = set()
alphabets = sorted(list(set(s)))
for c in alphabets:
    ins = all_index(s, c)
    for i in ins:
        for j in range(i, len(s)):
            if (j+1 - i) > k:
                break

            ss.add(s[i:j+1])

    if len(ss) >= k:
        break

print((sorted(list(ss))[k-1]))
# Original solution
import sys
from string import ascii_lowercase as AL

input = sys.stdin.readline


def main():
    s = input().rstrip()
    K = int(eval(input()))

    N = len(s)
    total = 0
    for al in AL:
        induces = []
        for i in range(N):
            if al == s[i]:
                induces.append(i)
        if not induces:
            continue
        match = [al]
        for i in range(1, 5):
            for idx in induces:
                if idx + i < N:
                    match.append(s[idx:idx + i + 1])
        match = set(match)
        match = sorted(match)
        if total + len(match) >= K:
            ans = match[K - 1 - total]
            break
        else:
            total += len(match)
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys

input = sys.stdin.readline


def main():
    s = input().rstrip()
    K = int(eval(input()))

    N = len(s)
    sub = []
    for i in range(N):
        for j in range(K):
            sub.append(s[i:i+j+1])
    sub = set(sub)
    sub = sorted(sub)
    ans = sub[K-1]
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import sys
from string import ascii_lowercase as AL

input = sys.stdin.readline


def main():
    S = input().rstrip()
    K = int(eval(input()))

    N = len(S)
    sub = set()
    for al in AL:
        for i in range(N):
            if S[i] == al:
                for j in range(1, 6):
                    sub.add(S[i:i + j])
        if len(sub) >= K:
            break

    sub = sorted(sub)
    ans = sub[K - 1]

    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys

input = sys.stdin.readline


def main():
    S = input().rstrip()
    K = int(eval(input()))

    N = len(S)
    sub = set()
    for i in range(N):
        for j in range(1, K + 1):
            sub.add(S[i:i + j])

    sub = sorted(sub)
    ans = sub[K - 1]

    print(ans)


if __name__ == "__main__":
    main()
# Original solution


import sys

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

s = list(input().strip())
K = int(eval(input()))
N = len(s)

if N == 1:
    print((s[0]))
    exit()
sub = set()
for i in range(N):
    for j in range(N):
        sub.add(''.join(s[i:j+1]))

print((sorted(sub)[K]))


# Optimized solution

S = input().strip()
K = int(eval(input()))
L = len(S)
substr = set()

for i in range(L):
    for j in range(5):
        s = S[i:min(i+j+1, L)]
        if s:
            substr.add(s)

print((sorted(substr)[K-1]))
# Original solution
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

s = stdin.readline().rstrip()
k = int(stdin.readline().rstrip())

def main():
    finish = set()
    S = len(s)
    for i in range(S):
        for j in range(i+1,S+1):
            finish.add(s[i:j])

    finish = list(finish)
    finish.sort()
    print((finish[k-1]))

if __name__ == "__main__":
    main()

# Optimized solution
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

s = stdin.readline().rstrip()
k = int(stdin.readline().rstrip())


finish = set()
S = len(s)

for i in range(S):
    for j in range(1,6):
        finish.add(s[i:i+j])

finish = list(finish)
finish.sort()

print((finish[k-1]))
# Original solution
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


A,B = MI()
S = LS2()

for i in range(A+B+1):
    if i == A:
        if S[i] != '-':
            print('No')
            break
    else:
        if S[i] == '-':
            print('No')
            break
else:
    print('Yes')


# Optimized solution
import sys
def MI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


A,B = MI()
S = LS2()

for i in range(A+B+1):
    if i == A:
        if S[i] != '-':
            print('No')
            break
    else:
        if S[i] == '-':
            print('No')
            break
else:
    print('Yes')
# Original solution
import sys
# import collections
# import math
import string
# import bisect
# import re
# import itertools
# import statistics

def main():
    a, b = (int(x) for x in sys.stdin.readline().split())
    s = sys.stdin.readline().rstrip()
    if s[a] == '-':
        s_a, s_b = s[:a], s[a+1:]
        for i in s_a:
            if not i in string.digits:
                f_a = False
                break
        else:
            f_a = True
            for i in s_b:
                if not i in string.digits:
                    f_b = False
                    break
            else:
                f_b = True
    else:
        print('No')
        exit()
    
    print(('Yes' if f_a and f_b else 'No'))

if __name__ == "__main__":
    # execute only if run as a script
    main()


# Optimized solution
import sys

a, b = list(map(int, sys.stdin.readline().split()))
s = sys.stdin.readline().rstrip()

def main():
    return 'Yes' if s[a] == '-' and not '-' in set(s[:a] + s[a+1:]) else 'No'

if __name__ == '__main__':
    ans = main()
    print(ans)
# Original solution
a=list(map(int,input().split()));t=list(map(len,input().split('-')));print(['No','Yes'][a==t])

# Optimized solution
print(['No','Yes'][list(map(int,input().split()))==list(map(len,input().split('-')))])
# Original solution
"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

A, B = list(map(int, readline().split()))
S = readline().decode('utf8').rstrip()
T=S[:A]+S[A+1:]
bl = S[A] == '-' and not('-' in T)

print(('Yes' if bl else 'No'))


# Optimized solution
"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

A, B = list(map(int, readline().split()))
S = readline().decode('utf8').rstrip()
T=S[:A]+S[A+1:]
bl = S[A] == '-' and T.find('-')==-1
print(('Yes' if bl else 'No'))
# Original solution
import re
a,b = list(map(int, input().split()))
s = input().split('-')
print(('Yes' if len(s)==2 and len(s[0])==a else 'No'))

# Optimized solution
a,b = list(map(int, input().split()))
s = input().split('-')
print(('Yes' if len(s)==2 and len(s[0])==a else 'No'))
# Original solution
import re,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
A,B = LI()
S = S()
print(('Yes' if re.fullmatch(pattern=r'\d{{{}}}-\d{{{}}}'.format(A,B),string=S) else 'No'))


# Optimized solution
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
A,B = LI()
S = S()
ans = 1
for i in range(A+B+1):
    if i==A:
        if S[i]!='-':
            ans = 0
            break
    else:
        if not S[i] in '1234567890':
            ans = 0
            break
print((['No','Yes'][ans]))
# Original solution
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: int, B: int, S: str):
    is_hyphen = True if S[A : A + 1] == "-" else False
    before = S[:A]
    after = S[A + 1 :]
    try:
        int(before)
        int(after)
        if is_hyphen:
            print(YES)
        else:
            print(NO)
    except:
        print(NO)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(A, B, S)


if __name__ == "__main__":
    main()


# Optimized solution
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(A: int, B: int, S: str):
    is_mid = True if S[A] == "-" else False
    is_num = (S[:A] + S[A + 1 :]).find("-") == -1
    print((YES if is_mid and is_num else NO))


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(A, B, S)


if __name__ == "__main__":
    main()
# Original solution
from collections import deque
n=int(input())
r=[list(map(int,input().split())) for _ in range(n)]
m=int(input())
pa=[list(map(int,input().split())) for _ in range(m)]
for i in range(m):
    d=[1]*n
    q=deque([pa[i][0]])
    used=[False]*n
    used[pa[i][0]-1]=True
    while len(q)!=0:
        f=0
        p=q.popleft()
        p-=1
        if d[p]==pa[i][2]:break
        for j in r[p][2:]:
            j-=1
            if pa[i][1]-1==j:
                f=1
                d[j]+=d[p]
                break
            if used[r[j][0]-1]:continue
            q.append(j+1)
            d[j]=d[p]+1
            used[j]=True
        if f==1:
            break
    if f==1:
        print((d[j]))
    else:
        print("NA")

# Optimized solution
n=int(input())
g=[[1000000]*n for _ in range(n)]
for i in range(n):
    g[i][i]=0
for i in range(n):
    r=list(map(int,input().split()))
    for j in r[2:]:
        g[r[0]-1][j-1]=1
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])
m=int(input())
for i in range(m):
    s,d,v=list(map(int,input().split()))
    s-=1
    d-=1
    if g[s][d]<v:
        print((g[s][d]+1))
    else:
        print('NA')
# Original solution
n=int(eval(input()))
count=0
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr
  
for i in make_divisors(n):
  if int(n)!=n or n==1:
    break
  if n%i==0 and len(factorization(i))==1:
    n=n/i
    count+=1
if count-1>=0:
  print((count-1))
else:
  print((0))
  

# Optimized solution
from collections import Counter
n=int(eval(input()))
def soin(n):
  soin_ans=[]
  while n%2==0:
    n//=2
    soin_ans.append(2)
  f=3
  while f<=n**0.5:
    if n%f==0:
      n//=f
      soin_ans.append(f)
    else:
      f+=2
  if n!=1:
    soin_ans.append(n)
  return soin_ans
s_list=soin(n)
s_set=set(s_list)
sc=Counter(s_list)
count=0
for i in s_set:
  for j in range(1,sc[i]+1):
    if n%i**j==0:
      n//=i**j
      count+=1
print(count)
# Original solution
n = int(eval(input()))
ans = 0
i = 2

while n>1 and i*i<=n:
  if n % i == 0:
    c = 0
    while n % i == 0:
      n = n / i
      c = c + 1
    Y=1
    U=2
    while c>=Y:
      ans=ans+1
      Y=Y+U
      U=U+1

  i = i + 1
      
    
if n > 1:
  ans = 1 + ans

print(ans)

# Optimized solution
n = int(eval(input()))
ans = 0
i = 2

while n>1 and i*i<=n:
  if n % i == 0:
    c = 0
    while n % i == 0:
      n = n / i
      c = c + 1
    Y=1
    U=2
    while c>=Y:
      ans=ans+1
      Y=Y+U
      U=U+1

  i += 1
      
    
if n > 1:
  ans = 1 + ans

print(ans)
# Original solution
n = int(eval(input()))
ans = 0
i = 2

while n>1 and i*i<=n:
  if n % i == 0:
    c = 0
    while n % i == 0:
      n = n / i
      c += 1
    Y=1
    U=2
    while c>=Y:
      ans=ans+1
      Y=Y+U
      U=U+1

  i = i + 1
      
    
if n > 1:
  ans = 1 + ans

print(ans)
  

# Optimized solution
n = int(eval(input()))
ans = 0
i = 2
 
while n>1 and i*i<=n:
  if n % i == 0:
    c = 0
    while n % i == 0:
      n = n / i
      c += 1
    j = 1
    while c>=j:
      ans=ans+1
      c -= j
      j += 1
 
  i = i + 1
      
    
if n > 1:
  ans = 1 + ans
 
print(ans)
# Original solution
import sys
N = int(sys.stdin.readline().rstrip())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors

def prime_judge(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)
    a = set(a)
    if len(a) == 1:
        return True
    else:
        return False

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)
    a = set(a)
    if len(a) == 1 and prime_judge(list(a)[0]):
        return True
    else:
        return False

divisors = make_divisors(N)
ans = 0
for d in divisors:
    if prime_factorize(d) and N % d == 0 and N // d > 0:
            N //= d
            ans += 1
print(ans)


# Optimized solution
import sys
N = int(sys.stdin.readline().rstrip())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors

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)
    a = set(a)
    if len(a) == 1:
        return True
    else:
        return False

divisors = make_divisors(N)
ans = 0
for d in divisors:
    if prime_factorize(d) and N % d == 0:
        N //= d
        ans += 1
print(ans)
# Original solution
import sys
N = int(sys.stdin.readline().rstrip())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors

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)
    a = set(a)
    if len(a) == 1:
        return True
    else:
        return False

divisors = make_divisors(N)
ans = 0
for d in divisors:
    if prime_factorize(d) and N % d == 0:
        N //= d
        ans += 1
print(ans)

# Optimized solution
import sys
N = int(sys.stdin.readline().rstrip())

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

primes = prime_factorize(N)

from collections import Counter

cnts = Counter(primes)
ans = 0
for p, cnt in list(cnts.items()):
    tmp = 1
    while cnt - tmp >= 0:
        cnt -= tmp
        tmp += 1
        ans += 1
print(ans)
# Original solution
import math
N = int(eval(input()))
if N == 1:
    print((0))
    exit()
div = {}
i = 2
while i*i <= N:
    while N % i == 0:
        N = N // i
        if i in div:
            div[i] += 1
        else:
            div[i] = 1
    if N == 1:
        break
    i += 1
if N != 1:
    div[N] = 1
ans = 0
for v in list(div.values()):
    i = 1
    while v >= i:
        v -= i
        i += 1
        ans += 1
print(ans)


# Optimized solution
import math
N = int(eval(input()))
if N == 1:
    print((0))
    exit()
div = {}
for i in range(2, int(math.sqrt(N))+1):
    while N % i == 0:
        N = N // i
        if i in div:
            div[i] += 1
        else:
            div[i] = 1
    if N == 1:
        break
if N != 1:
    div[N] = 1
ans = 0
for v in list(div.values()):
    i = 1
    while v >= i:
        v -= i
        i += 1
        ans += 1
print(ans)
# Original solution
def find_primes(n):
    ps = []
    t = [True] * n
    t[0] = t[1] = False
    for i in range(2, n):
        if not t[i]:
            continue
        ps.append(i)
        for j in range(i, n, i):
            t[j] = False
    return ps


def solve(string):
    n = int(string)
    if n == 1:
        return "0"
    rn = int(n**0.5 + 1)
    ps = find_primes(rn)
    ans = 0
    for i in ps:
        k = 1
        while n % (i**k) == 0:
            ans += 1
            n //= i**k
            k += 1
    return str(ans + (n >= rn))


if __name__ == '__main__':
    import sys
    print((solve(sys.stdin.read().strip())))


# Optimized solution
import collections

n = int(eval(input()))

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

if n == 1: # 1
    print((0))
    exit()

c = collections.Counter(prime_factorize(n))
_, counts = list(zip(*c.most_common()))

l = list(counts)
ans = 0

if l == [1]: # prime number
    print((1))
    exit()

for i in l:
    for j in range(1, i+1):
        if i >= j:
            i -= j
            ans += 1

print(ans)
# Original solution
import math
def get_prime(n):
    if n <= 1:
        return []
    prime = [2]
    if n > 2:
        limit = int(math.sqrt(n))
        odd = [i for i in range(3, n + 1, 2)]
        while limit >= odd[0]:
            prime.append(odd[0])
            odd = [j for j in odd if j % odd[0] != 0]
        prime += odd
    return prime

from collections import defaultdict
def prime_factorization(n):
    if n <= 1:
        return {}
    else:
        # print(int(math.sqrt(n)))
        prime = get_prime(int(math.sqrt(n)))
        dct = defaultdict(int)
        for p in prime:
            while n % p == 0:
                dct[p] += 1
                n //= p
        if n != 1:
            dct[n] += 1
        dct = dict(dct)
        return dct

n = int(eval(input()))
pf = prime_factorization(n)

Z = []
for k, v in list(pf.items()):
    for i in range(1, v + 1):
        Z.append(k ** i)
Z.sort()
count = 0
for z in Z:
    if n % z == 0:
        count += 1
        n //= z


print(count)

# Optimized solution
def p_facto(n):
    ret = []
    nc = n
    for i in range(2, nc):
        if i*i > nc:
            break
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            ret.append([i, ex])
    if n != 1:
        ret.append([n, 1])
    return ret


def main(N):
    ans = 0
    for p, e in pf:
        ex = 1
        while True:
            z = p**ex
            if N % z == 0:
                ans += 1
                N //= z
            else:
                break
            ex += 1
    print(ans)


if __name__ == "__main__":
    N = int(eval(input()))
    pf = p_facto(N)
    main(N)