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

import numpy as np

def split(ar, k, w):
    a = 0
    if np.sum(ar>k) > 0:
        return -1
    tm = ar[0]
    for i in range(1, w):
        tm += ar[i]
        if np.sum(tm > k) > 0:
            a += 1
            tm = ar[i]
    return a
            

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
s = np.array(s)
ans = h*w

for i in range(2**(h-1)):
    data = []
    temp = s[0].copy()
    sp = bin(i+2**h)[4:]
    if ans <= sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp += s[j]
        else:
            data.append(temp)
            temp = s[j].copy()
    data.append(temp)
    ans_ = split(np.array(data).T, k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

### FIXED CODE ###

def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def check_overk(in1, k):
    return len([i for i in in1 if i>k]) > 0

def split(ar, k, w):
    a = 0
    for i in ar:
        if check_overk(i, k):
            return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if check_overk(tm, k):
            a += 1
            tm = ar[i]
    return a
            

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
ans = h*w

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)
### BUGGY CODE ###

# get initial input parameter
n, k, q = map(int, input().split())

# init point
point_list = [ k for _ in range(n) ]

for round in range(q):
    # get correct answer persion
    person_index = int(input()) - 1
    
    # point decrement
    point_list = [ point_list[i] - 1 if i != person_index else point_list[i] for i in range(n) ]

for item in point_list:
    if (0 < item):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

# get initial input parameter
n, k, q = map(int, input().split())
 
# init point
point_list = [ (k - q) for _ in range(n) ]
 
for round in range(q):
    # get correct answer persion
    person_index = int(input()) - 1
    
    # point decrement
    point_list[person_index] += 1
 
for item in point_list:
    if (0 < item):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import bisect

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

b = []
for ai in a:
    bisect.insort(b,ai )
# print(b)

for i in range(m):
    tmp = b.pop()//2
    bisect.insort(b, tmp)
    # print(b)

print(sum(b))

### FIXED CODE ###

import heapq
import math

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

b = []
for ai in a:
    heapq.heappush(b, ai* -1)
# print(b)

for i in range(m):
    tmp = math.ceil(heapq.heappop(b)/2)
    heapq.heappush(b, tmp)
    # print(b)

print(sum(b) * -1)
### 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()

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

def main():
  n=I()
  l=LI()

  a=1
  for x in l:
    a=lcm(a,x)

  ans=0
  for x in l:
    ans+=a//x

  return ans%mod

# 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 lcm(a,b): return a*b//fractions.gcd(a,b)

def main():
  n=I()
  l=LI()

  a=1
  for x in l:
    a=lcm(a,x)

  ans=0
  for x in l:
    ans+=a//x

  return ans%mod

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

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

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = ((k // i) ** n) % M
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    
# print(sum((i)*nums[i]%M for i in range(len(nums)))%M)
print((np.arange(k+1) * nums).sum()%M)

### FIXED CODE ###

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

import numpy as np
M = int(10**9)+7
n,k = [int(c) for c in input().split()]
nums = [0]*(k+1)
nums = np.zeros((k+1), dtype=int)
for i in range(k, 0, -1):
    tmp = pow(k // i, n, M)
    tmp -= nums[(2*i)::i].sum()
    nums[i] += tmp
    
# print(sum((i)*nums[i]%M for i in range(len(nums)))%M)
print((np.arange(k+1) * nums).sum()%M)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=1
for i in range(n):
    b*=a[i]
if(b>10**18):
    print('-1')
else:
    print(b)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=1
flag=-1
for i in range(n):
    b*=a[i]
    if(flag==-1):
        flag=1
        if(0 in a):
            flag=2
            break
    if(b>10**18):
        flag=0
        break
if(flag==0):
    print(-1)
if(flag==1):
    print(b)
if(flag==2):
    print(0)
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        # self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

N,Q = map(int,input().split())
c = list(map(int,input().split()))

query = []

for i in range(Q):
    l,r = map(int,input().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

    ###
    #print(i,ans)
    ###
    
for i in range(Q):
    print(ans[i])





### FIXED CODE ###

from sys import stdin

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        # self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

N,Q = map(int, stdin.readline().split())
c = list(map(int, stdin.readline().split()))

query = []

for i in range(Q):
    l,r = map(int, stdin.readline().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

    ###
    #print(i,ans)
    ###
    
'''
for i in range(Q):
    print(ans[i])
'''

print(*ans,sep='\n')
### BUGGY CODE ###

def main():
    n = int(input())
    words = {}
    for _ in range(n):
        a = input()
        if a in words:
            words[a] += 1
        else:
            words[a] = 1
    results = [key
               for key in words.keys() if words[key] == max(words.values())]
    results.sort()
    print(' '.join(map(str, results)))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n = int(input())
    words = {}
    for _ in range(n):
        a = input()
        if a in words:
            words[a] += 1
        else:
            words[a] = 1
    max_val = 0
    results = []
    for i in words.keys():
        if words[i] > max_val:
            max_val = words[i]
            results = []
            results.append(i)
        elif words[i] == max_val:
            results.append(i)

            # results = [key
            #            for key in words.keys() if words[key] == max(words.values())]
            # results.sort()
    results.sort()
    print('\n'.join(map(str, results)))


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

import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      q.append((i,j))
#print(start)
x=0
y=maze[:]

for i in q:
  maze[i[0]][i[1]]=0
while(q):
  c=q.popleft()
  for j in range(4):
    if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
      if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
        q.append((c[0]+dy[j],c[1]+dx[j]))
        maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
        
        x=max(x,maze[c[0]+dy[j]][c[1]+dx[j]])
print(x)

### FIXED CODE ###

import sys
from collections import deque
H,W=map(int,input().split())
A=[[c for c in l.strip()] for l in sys.stdin]
maze=[[3000]*W for i in range(H)]
q=deque([])
start=[]
dy=[1,0,-1,0]
dx=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    if(A[i][j]=="#"):
      q.append((i,j))
#print(start)
x=0
y=maze[:]

for i in q:
  maze[i[0]][i[1]]=0
while(q):
  c=q.popleft()
  for j in range(4):
    if(c[0]+dy[j]>=0 and c[0]+dy[j]<H and c[1]+dx[j]>=0 and c[1]+dx[j]<W):
      if(maze[c[0]+dy[j]][c[1]+dx[j]]==3000 and A[c[0]+dy[j]][c[1]+dx[j]]=="."):
        q.append((c[0]+dy[j],c[1]+dx[j]))
        maze[c[0]+dy[j]][c[1]+dx[j]]=maze[c[0]][c[1]]+1
        
        x=max(x,maze[c[0]+dy[j]][c[1]+dx[j]])
print(x)
### BUGGY CODE ###

M=1000000007
s=0
n=int(input())
a=list(map(int,input().split()))
for i in range(n-1):
    for j in range(i+1,n):
        s+=(a[i]*a[j])
print(s%M)
        
    

### FIXED CODE ###

M=1000000007
def findProductSum(A, n): 
    s = 0
    for i in range(n): 
        s+=A[i] 
    array_sum_square = s*s
    individual_square_sum = 0
    for i in range(n): 
        individual_square_sum += A[i]*A[i]
    return (array_sum_square -individual_square_sum) // 2
n=int(input())
a=list(map(int,input().split()))
print(findProductSum(a,n)%M)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
se = 1
for n in range(N):
  se *= A[n]
if se >  10**18:
  print("-1")
else:
  print(se)

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
se = 1
c = True
for n in range(N):
  se *= A[n]
  if se >  10**18:
    c = False
    break
for n in range(N):
  if A[n] == 0:
    se = 0
    c = True
if c:
  print(se)
else:
  print("-1")
### BUGGY CODE ###

A,B,C = map(int,input().split())
maxi = max(A,B,C)
mini = min(A,B,C)
mid = sum([A,B,C]) - (maxi+mini)
i,j,k,l = 0,0,0,0
if mini%2 != mid%2:
    #midだけ偶奇が違うとき
    if maxi%2 == mini%2 and maxi%2 != mid%2:
        while mid - maxi != 1:
            mid += 2
            i += 1
    #miniだけ偶奇が違うとき
    if maxi%2 != mini%2 and maxi%2 == mid%2:
        while mini - maxi != 1:
            mid += 2
            j += 1
while maxi - mini > 1:
    mini += 2
    k += 1
while maxi - mid > 1:
    mid += 2
    l += 1
if maxi == mini and maxi == mid:
    print(i+j+k+l)
else:
    print(i+j+k+l+1)

### FIXED CODE ###

A,B,C = map(int,input().split())
maxi = max(A,B,C)
mini = min(A,B,C)
mid = sum([A,B,C]) - (maxi+mini)
i,j,k,l = 0,0,0,0
if mini%2 != mid%2:
    #midだけ偶奇が違うとき
    if maxi%2 == mini%2 and maxi%2 != mid%2:
        if mid - maxi != 1:
            i = (maxi+1-mid)//2
            mid = maxi + 1
    #miniだけ偶奇が違うとき
    if maxi%2 != mini%2 and maxi%2 == mid%2:
        if mini - maxi != 1:
            j = (maxi+1-mini)//2
            mini = maxi + 1
while maxi - mini > 1:
    mini += 2
    k += 1
while maxi - mid > 1:
    mid += 2
    l += 1
if maxi == mini and maxi == mid:
    print(i+j+k+l)
else:
    print(i+j+k+l+1)
### BUGGY CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
DP[t][d][m] = 1
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t, -1, -1):
    for k in range(N, -1, -1):
      x = DP[i][j][k]
      y = D[i][j][k]
      if x != 0:
        if i + j + k != 0:
          su += y * N /(i + j + k)
        if i >= 1:
          DP[i - 1][j + 1][k] += x
          D[i - 1][j + 1][k] += y * i / (i + j + k)
        if j >= 1: 
          DP[i][j - 1][k + 1] += x
          D[i][j - 1][k + 1] += y * j / (i + j + k)
        if k >= 1:
          DP[i][j][k - 1] += x
          D[i][j][k - 1] += y * k / (i + j + k)

print(su)


### FIXED CODE ###

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

m = d = t = 0
for i in range(len(a)):
  if a[i] == 1:
    m += 1
  elif a[i] == 2:
    d += 1
  else:
    t += 1

D = [[[0] * (N + 1) for i in range(d + t + 1)] for j in range(t + 1)]
su = 0
D[t][d][m] = 1
for i in range(t, -1, -1):
  for j in range(d + t - i, -1, -1):
    for k in range(N - i - j, -1, -1):
      y = D[i][j][k]
      if i + j + k != 0:
        su += y * N /(i + j + k)
      if i >= 1:
        D[i - 1][j + 1][k] += y * i / (i + j + k)
      if j >= 1: 
        D[i][j - 1][k + 1] += y * j / (i + j + k)
      if k >= 1:
        D[i][j][k - 1] += y * k / (i + j + k)

print(su)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(a-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000000)

import sys
input = sys.stdin.readline

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N-1)]
px = [list(map(int,input().split())) for _ in range(Q)]

query = [0] * N
ans = [0] * N

for p,x in px:
    query[p-1] = query[p-1] + x
    
adj_list = [[] for _ in range(N)]
for a,b in ab:
    adj_list[a-1].append(b-1)
    adj_list[b-1].append(b-1)

memo = [True] * N

def dfs(v,val):
    child = adj_list[v]
    memo[v] = False
    val += query[v]
    ans[v] = val
    for s in child:
        if memo[s]:
            dfs(s,val)
    return 
        
dfs(0,0)
print(*ans)
### BUGGY CODE ###

import os, sys, re, math

N, M = [int(s) for s in input().split(' ')]

cards = [int(s) for s in input().split(' ')]
cards.sort()

bc_ary = []
for i in range(M):
    bc_ary.append([int(s) for s in input().split(' ')])

for bc in bc_ary:
    cnt = 0
    idx = 0
    while idx < N and cnt < bc[0]:
        mincard = min(cards)
        if mincard < bc[1]:
            cards[cards.index(mincard)] = bc[1]
            cnt += 1
        idx += 1

print(sum(cards))


### FIXED CODE ###

import os, sys, re, math, heapq

N, M = [int(s) for s in input().split(' ')]

dic = {}
cards =  [int(s) for s in input().split(' ')]
for c in cards:
    if c in dic:
        dic[c] += 1
    else:
        dic[c] = 1

for i in range(M):
    b,c = [int(s) for s in input().split(' ')]
    if c in dic:
        dic[c] += b
    else:
        dic[c] = b

keys = sorted(list(dic.keys()), reverse=True)

ret = 0
for k in keys:
    ret += min(N, dic[k]) * k
    N = N - dic[k]
    if N <= 0:
        break

print(ret)
### BUGGY CODE ###

import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)

Max_h = h_lst[0][0]
memo = set(memo)
              

for [y,j] in h_lst:
  if y == Max_h:
    for [z,k] in w_lst:
      if (j,k) not in memo and w_lst[0][0] == z:
        print(Max_h+w_lst[0][0])
        sys.exit()
print((Max_h+w_lst[0][0])-1)        
  

### FIXED CODE ###

import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0][1]]
w_ans = [w_lst[0][1]]
if h != 1:
  s = 1
  while s < h and h_lst[s][0] == Max_h:
    h_ans.append(h_lst[s][1])
    s+= 1  
if w!= 1:  
  t=1  
  while t < w and w_lst[t][0] == Max_w:
    w_ans.append(w_lst[t][1])
    t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for j in h_ans:
  for k in w_ans:
    if (j,k) not in memo:
      print(Max_h+Max_w)
      sys.exit()
print((Max_h+Max_w)-1)
### BUGGY CODE ###

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

M = 10**9 + 7
ans = 0

for i in range(N-1):
    for n in range(i + 1, N):
        ans += A[i] * A[n]
    ans = ans % M

print(ans)

### FIXED CODE ###

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

M = 10**9 + 7

Total = sum(A) -A[0]

ans = 0

for i in range(N-1):
    ans += A[i] * Total
    ans = ans % M
    Total -= A[i+1]

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

from collections import Counter
import math
n=int(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

s=dict(Counter(prime_factorize(n)))
#print(s)
sum_ans=0
for i in s.values():
  
  if i==1:
    sum_ans+=1
    
  else:
    k=1
    while i:
      i-=k
      k+=1
      #print(i)
      sum_ans+=1
      
print(sum_ans)
      

### FIXED 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
  
from collections import Counter
n=int(input())
s=Counter(prime_factorize(n))
t=list(s.values())
cnt=0
#print(s)
#print(t)
for i in t:
  if i==1:
    cnt+=1
    
  else:
    s=1
    while i>0:
      i=i-s
      s+=1
      if i<0:
        break
      cnt+=1
      
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split())
ans=n
a=[]
if k==1:
  print(0)
elif abs(n-k) > n:
  print(n)
else:
  while len(a)==len(set(a)):
    n=abs(n-k)
    a.append(n)
    ans=min(ans,n)
  print(ans)

### FIXED CODE ###

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

a=n%k
ans=min(a,k-a)
print(ans)
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))
num = 0

for i in range(N):
  for j in range(i):
    if List[i] > List[j]:
      break
  else:
    num += 1
print(num)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
num = 0
min = List[0]
for i in range(N):
  if List[i] <= min:
    num += 1
    min = List[i]
print(num)
### BUGGY CODE ###

N = int(input())
L = []
for i in range(N):
  L.append(input())
l = list(set(L))
l.sort()
c = [L.count(j) for j in l]
C = max(c)
[print(k) for k in l if L.count(k) == C]

### FIXED CODE ###

import collections
N = int(input())
l = [input() for i in range(N)]
L = collections.Counter(l)
a = L.most_common()
M = a[0][1]
A = [j[0] for j in a if j[1] == M]
[print(k) for k in sorted(A)]
### BUGGY CODE ###

import numpy as np
import copy

def main():
    data0 = np.array(list(input()))
    data1 = np.array(list(input()))

    flag = True
    data_tmp = data0
    for c0, c1 in zip(data0, data1):
        if list(data0 == c0) == list(data1 == c1):
            pass
        else:
            flag = False

    if flag:
        print('Yes')
    else:
        print('No')



def swap(data, c0, c1):
    data_tmp = copy.copy(data)
    data_tmp[data == c0] = c1
    data_tmp[data == c1] = c0
    return data_tmp

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    data0 = input()
    data1 = input()

    flag = True
    data_tmp = data0
    count = 0
    len_data = len(data0)
    while True:
        if data0 == "":
            break

        data0 = data0.replace(data0[0], "")
        data1 = data1.replace(data1[0], "")

        if len(data0) != len(data1):
            print('No')
            exit()

    print('Yes')

if __name__ == "__main__":
    main()