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

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ans = 0
    d = defaultdict(int)
    d[1] = 1 
    for i in range(2, int(sqrt(n - 1)) + 2):
        x = i
        while 1:
            if n % x == 0 and d[x] != 1:
                ans += 1
                n //= x
                d[x] = 1
            else:
                break
            x *= i
        l = i
        for i in range(i + 1):
            d[l*i] = 1
    if d[n]:
        print(ans)
    else:
        print(ans + 1)
    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    n = II()
    ans = 0
    N = int(sqrt(n))+2
    d = defaultdict(int)
    d[1] = 1 
    for i in range(2, int(sqrt(n - 1)) + 2):
        if d[i] == 0:
            x = i
            while 1:
                if n % x == 0 and d[x] != 1:
                    ans += 1
                    n //= x
                    d[x] = 1
                else:
                    break
                x *= i
            l = i
            j = 1
            while l < N:
                d[l] = 1
                j += 1
                l = i * j
    if d[n]:
        print(ans)
    else:
        print(ans + 1)
    return


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

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

C = [0] * n

for a in range(q) :
    C[int(input())-1] += 1

for i in range(n) :
    minus = sum(C) - C[i]
    if minus < k :
        print('Yes')
    else :
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
 
C = [0] * n
 
for a in range(q) :
    C[int(input())-1] += 1
 
sum_c = sum(C)
 
for i in range(n) :
    minus = sum_c - C[i]
    if minus < k :
        print('Yes')
    else :
        print('No')
### BUGGY CODE ###

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

a = []
for i in range(m):
    a.append(int(input()))

dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])

### FIXED CODE ###

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

a = []
for i in range(m):
    a.append(int(input()))
a = set(a)

dp = [0] * (n + 1)
dp[0] = 1
for now in range(0, n + 1):
    for next_step in range(now + 1, min(n + 1, now + 3)):
        if not next_step in a:
            dp[next_step] += dp[now]
            dp[next_step] %= 1000000007

print(dp[n])
### BUGGY CODE ###

number = input()

heights = input().split(' ')

heights = [int(x) for x in heights]



count = 0

temp = 0

for n in range (0, int(number)):
    temp_count = 0
    for i in range (n, int(number)):
        if i == 0:
            continue
        if heights[i] <= heights[i-1]:
            temp_count += 1
        else:
            break
    if temp_count > count:
        count = temp_count

print (count)

### FIXED CODE ###

number = input()

heights = input().split(' ')

heights = [int(x) for x in heights]



count = 0

temp = 0

nxt_pos = 0

for n in range (0, int(number)):
    if n <= nxt_pos:
        continue
    if count > len(heights) - n:
        break
    temp_count = 0
    for i in range (n, int(number)):
        if i == 0:
            continue
        if heights[i] <= heights[i-1]:
            temp_count += 1
        else:
            nxt_pos = i
            break
    if temp_count > count:
        count = temp_count

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

mod=10**9+7
s=input()


d=[0 for _ in range(13)]
p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=s[::-1]
num=rev.find("?")
if num==-1:
    b=int(s.replace("?","0"))%13
    if b<=5:
        cal=5-b
    else:
        cal=18-b
    if cal==0:
        print(1)
    else:
        print(0)
else:
    b=0
    tmp=10**num%13
    for i in p[tmp]:
        d[i]+=1
    for i,v in enumerate(rev):
        #print(i+num+1)
        if v=="?" and i>num:
            tmp=10**i%13
            t_d=[0 for _ in range(13)]
            #print("i,tmp:",i+num+1,",",tmp)
            for k in range(0,13):
                for j in range(0,10):
                    t_d[(p[tmp][j]+k)%13]+=d[k]
                #print(t_d)
            #for j in range(13):
                #d[j]=t_d[j]
            d=t_d
            #print(t_d)
        elif v=="?":
            pass
        else:
            b+=int(v)*10**i%13
    b%=13
    if b<=5:
        cal=5-b
    else:
        cal=18-b
    #print(b)
    #print(cal)
    #print(d[7]%mod)
    print(d[cal]%mod)

### FIXED CODE ###

#%%time
mod=10**9+7
s=input()


#p=[[i*j%13 for i in range(10)] for j in range(13)]
rev=reversed(s)
d=[0 for i in range(13)]
d[0]=1
keep=[0 for _ in range(13)]
mul=1
cal=0
for v in rev:
    #print(i+num+1)
    if v=="?":
        t_d=[0 for _ in range(13)]
        #print("i,tmp:",i+num+1,",",tmp)
        for k in range(0,13):
            for j in range(0,10):
                t_d[(mul*j+k)%13]+=d[k]
            t_d[k]%=mod
        d=t_d
    else:
        cal+=mul*int(v)%13
    mul*=10
    mul%=13
        #print(t_d)
cal%=13
if cal<=5:
    cal=5-cal
else:
    cal=18-cal
print(d[cal]%mod)
#print(d)
#h=d
#print([i%mod for i in h])
### BUGGY CODE ###

MAX = 2*10**5
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
s_map = [0 for i in range(MAX+1)]
def solve(n):
    if n == 0:
        return 1
    if s_map[n] > 0:
        return s_map[n]
    s_map[n] = 1 + solve(n % popcount(n))
    return s_map[n]

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
for i in range(N):
    c_p_cnt = p_cnt+1 if X[i] == '0' else p_cnt-1
    x = num_x + 2**(N-1-i) if X[i] == '0' else num_x - 2**(N-1-i)
    if x == 0:
        print(0)
    else:
        print(solve(x % c_p_cnt))



### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")
def solve(n):
    if n == 0:
        return 0
    return 1+solve(n % popcount(n))

N = int(input())
X = input()
num_x = int(X, 2)
p_cnt = X.count('1')
if p_cnt == 1:
    for i in range(N):
        if X[i] == '1':
            print(0)
        elif i == N-1:
            print(2)
        else:
            print(1)
    exit()
r0_p = num_x % (p_cnt+1)
r0_m = num_x % (p_cnt-1)
for i in range(N):
    if X[i] == '0':
        c_p_cnt = p_cnt+1
        r = (r0_p + pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    else:
        c_p_cnt = p_cnt-1
        if c_p_cnt == 0:
            print(0)
            continue
        r = (r0_m- pow(2, (N - 1 - i), c_p_cnt)) % c_p_cnt
    print(1 + solve(r % c_p_cnt))
### BUGGY CODE ###

from functools import *
from collections import *
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)

M = 10**9+7

@lru_cache(maxsize=None)
def mod_inv(a):
  b, x, y = M, 1, 0
  while a != 1:
    (d, a), b = divmod(b, a), a
    x, y = y-d*x, x
  return x%M

cache = defaultdict(dict)
def calc_cache(root, parent):
  c = cache[root]
  if not c or parent in c:
    return
  
  if c and None not in c:
    for p, (r2, t2, s2) in c.items():
      r3, t3, s3 = calc_subtree(p, root)
      r = r2 * t3
      s = s2 + s3
      c[None] = r, None, s
      break
  
  if parent is None:
    return
  
  if None in c:
    r0, t0, s0 = c[None]
    r1, t1, s1 = calc_subtree(parent, root)
    r = r0 * mod_inv(t1) % M
    s = s0 - s1
    c[parent] = r, r * mod_inv(s) % M, s

  
def calc_subtree(root, parent):
  calc_cache(root, parent)
  
  if parent in cache[root]:
    return cache[root][parent]
  
  ret = 1
  size = 1
  for child in (Edge[root] - {parent}):
    r, t, s = calc_subtree(child, root)
    ret = ret * t % M
    size += s
  cache[root][parent] = ret, ret * mod_inv(size) % M if parent else None, size
  return cache[root][parent]

N = int(input())
Edge = defaultdict(set)
fact = 1
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)

for i in range(1, N+1):
  print(calc_subtree(i, None)[0] * fact % M)


### FIXED CODE ###

from functools import *
from collections import *
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
 
M = 10**9+7

@lru_cache(maxsize=None)
def mod_inv(a):
  b, x, y = M, 1, 0
  while a != 1:
    (d, a), b = divmod(b, a), a
    x, y = y-d*x, x
  return x%M

@lru_cache(maxsize=None)
def calc_subtree(v):
  ret = 1
  size = 1
  for child in Edge[v]:
    Edge[child].remove(v)
    r, s = calc_subtree(child)
    ret = ret * r % M
    size += s
      
  ret = ret * size % M
  return ret, size

ans = {}
def set_ans(v, a):
  ans[v] = a
  for child in Edge[v]:
    n = calc_subtree(child)[1]
    set_ans(child, ans[v] * n * mod_inv(N-n) % M)

N = int(input())
Edge = defaultdict(set)
fact = N
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)

set_ans(1, mod_inv(calc_subtree(1)[0]) * fact % M)
for i in range(1, N+1):
  print(ans[i])
### BUGGY CODE ###

h, n = map(int, input().split())
magics = []
for i in range(n):
    a, b = map(int, input().split())
    magics.append((a, b))
h_table = [float("inf") for _ in range(h + 1)]
h_table[0] = 0
for i in range( h + 1):
    for a, b in magics:
        h_table[min(i + a, h)] = min(h_table[min(i + a, h)], h_table[i] + b)
print(h_table[h])


### FIXED CODE ###

h, n = map(int, input().split())
magics = []
for i in range(n):
    a, b = map(int, input().split())
    magics.append((a, b))
h_table = [float("inf") for _ in range(h + 1)]
h_table[0] = 0
for i in range( h + 1):
    for a, b in magics:
        h_table[min(i + a, h)] = min(h_table[min(i + a, h)], h_table[i] + b)
print(h_table[h])
### BUGGY CODE ###

n = int(input())
ls=[int(input()) for i in range(n)]
ans=[]
for i in range(n):
  ls2 = ls.copy()
  del ls2[i]
  ans.append(max(ls2))
for i in range(n):
  print(ans[i])


### FIXED CODE ###

n = int(input())
ls=[int(input()) for i in range(n)]
maxn = max(ls)
ans=[maxn]*n
nma = ls.index(maxn)
ls2=ls.copy()
ls2.remove(maxn) 
maxcel= max(ls2)
del ans[nma]
ans.insert(nma,maxcel)
a='\n'.join(map(str,ans))
print(a)
### BUGGY CODE ###

num = [True]*(100001)
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

for i in range(100000, 1, -1):
  if not (num[i]):
    continue
  if not (num[int((i+1)/2)]):
    num[i] = False

for i in range(int(input())):
  _input = input().split(' ')
  sum = 0
  for i in range(int(_input[0]), int(_input[1])+1):
    if num[i]:
      sum = sum + 1
  print(sum)

### FIXED CODE ###

num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

for i in range(3, 100001):
  c[i] = c[i] + c[i-1]

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])
### BUGGY CODE ###

from heapq import *
def abc144c():
  n,k=map(int,input().split())
  a=sorted(list(map(int,input().split())))
  f=sorted(list(map(int,input().split())))[::-1]
  q=[] 
  for i,j in zip(a,f):
    heappush(q,(-i*j,j))
  for i in range(k):
    tmp,key=heappop(q)
    heappush(q,(tmp+key,key))
  ans,key=heappop(q)
  print(-ans)
abc144c()


### FIXED CODE ###

n,k=map(int,input().split())
abilities=sorted(list(map(int,input().split())))
foods=sorted(list(map(int,input().split())),reverse=True)

if sum(abilities)<=k:
  print(0)
  exit()
  
def check(score):
  ret=0
  for a,f in zip(abilities,foods):
    ret+=max(0,(a*f-score+f-1)//f)
  return ret<=k

ok=10**12+1
ng=0
for _ in range(50):
  mid=(ok+ng)//2
  if check(mid):
    ok=mid
  else:
    ng=mid
print(ok)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]

N_K = [K for i in range(N)]
for a in A:
    N_K = [n_k-1 if a-1 != i else n_k for i, n_k in enumerate(N_K)]

for n_k in N_K:
    if n_k <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [0]*N
# print(A)

for i in range(Q):
    A[int(input())-1] +=1
    # print(A)

for i in range(N):
    if K-Q+A[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

def findProductSum(A): 
    n=len(A)
    product = 0
    for i in range (n): 
        for j in range ( i+1,n): 
            product = product + A[i]*A[j] 
    return (product)%(1000000007) 
b=int(input())
A=list(map(int,input().split()))
print(findProductSum(A))

### FIXED CODE ###

def sumproductsofpairs(lst):
    total = 0
    psum = 0
    for x in lst:
        total += psum * x
        psum += x
    return total%(1000000007) 
b=int(input())
A=list(map(int,input().split()))
print(sumproductsofpairs(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
P = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    P[a - 1].append(b - 1)
    P[b - 1].append(a - 1)


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i % MOD
    dic[(n, k)] = ans % MOD
    return ans % MOD


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1)
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c)
    return ans % MOD


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c)

print(ans % MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

N, K = map(int, input().split())
P = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    P[a - 1].append(b - 1)
    P[b - 1].append(a - 1)


dic = {}


def Perm(n, k):
    if (n, k) in dic:
        return dic[(n, k)]
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
        ans %= MOD
    dic[(n, k)] = ans
    return ans


def dfs(g, p):
    ans = Perm(K - 2, len(P[p]) - 1)
    for c in P[p]:
        if not c == g:
            ans *= dfs(p, c)
            ans %= MOD
    return ans


ans = Perm(K, len(P[0]) + 1)
for c in P[0]:
    ans *= dfs(0, c)
    ans %= MOD

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

S = input()
Q = int(input())
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        S = S[::-1]
    else:
        if int(q[1]) == 1:
            S = q[2] + S
        else:
            S += q[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
cnt = 0
mae = []
usiro = []
for _ in range(Q):
    q = input().split()
    if len(q) == 1:
        cnt += 1
    else:
        if cnt % 2 == 0:
            if int(q[1]) == 1:
                mae.append(q[2])
            else:
                usiro.append(q[2])
        else:
            if int(q[1]) == 1:
                usiro.append(q[2])
            else:
                mae.append(q[2])

mae = mae[::-1]
S = "".join(mae) + S + "".join(usiro)

if cnt % 2 == 1:
    S = S[::-1]
print(S)
### BUGGY CODE ###

def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
A.sort()
lcm = 1
for i in A:
    lcm = (lcm*i)//GCD(lcm,i)
ans = 0
for i in A:
    ans += lcm//i
    ans %= MOD
print(ans)


### FIXED CODE ###

def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)

def func(x):
    if x <= 1:
        return []
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            count = 0
            while x%i==0:
                x //= i
                count += 1
            return [[i,count]]+func(x)
    return [[x,1]]
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = [0]*(10**6)
for i in A:
    for a,b in func(i):
        lcm[a] = max(lcm[a],b)
L = 1
for i in range(2,10**6):
    L *= pow(i,lcm[i],MOD)
    L %= MOD
ans = 0
for i in A:
    ans += L*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 1
for i in range(1,N):
    if P[i] < min(P[0:i]): cnt += 1
print(cnt)

### FIXED CODE ###

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

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
import sys
input = sys.stdin.readline

N,M = two_int()

inputs =[]

dicts={}

for i in range(M):
    P,S = two_int()
    inputs.append([P,S])
    
    if P not in dicts:
        dicts[P]=[]
    
    if S not in dicts[P]:
        dicts[P].append(S)
    


#各県でsort
pref_strs={}
for k, v in dicts.items():
    dicts[k]=sorted(dicts[k])
    pref_strs[k]=str(k).zfill(6)



import bisect

for i in inputs:
    P,S=i
    
    city_index = bisect.bisect_right(dicts[P], S)
    city_str=str(city_index)
    
    print(pref_strs[P]+city_str.zfill(6))

### FIXED CODE ###

def two_int():
    N, K = map(int, input().split())
    return N,K

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))
import sys
input = sys.stdin.readline

N,M = two_int()

inputs =[]

dicts={}

for i in range(M):
    P,S = input().split()
    S=int(S)
    inputs.append([P,S])
    
    if P not in dicts:
        dicts[P]=[]
    
    dicts[P].append(S)
    


#各県でsort
pref_strs={}
for k, v in dicts.items():
    dicts[k]=sorted(dicts[k])
    pref_strs[k]=k.zfill(6)

import bisect

for i in inputs:
    P,S=i
    
    city_index = bisect.bisect_right(dicts[P], S)
    city_str=str(city_index)
    
    print(pref_strs[P]+city_str.zfill(6))
### BUGGY CODE ###

n = int(input())
ans = []

for i in range(n):
    a = int(input())
    if a in ans:
        ans.remove(a)
    else:
        ans.append(a)

print(len(ans))


### FIXED CODE ###

n = int(input())
ans = set()

for i in range(n):
    a = int(input())
    if a in ans:
        ans.remove(a)
    else:
        ans.add(a)

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

import sys
input=sys.stdin.readline
from operator import itemgetter

N, M = [int(x) for x in input().split()]
A = []
for _ in range(N):
    A.append([int(x) for x in input().split()])

A_sorted = sorted(A, key=itemgetter(0))

total = 0
for x in range(1, M + 1):
    max = 0
    max_index = -1
    for y, row in enumerate(A_sorted):
        if row[0] <= x:
            if row[1] > max:
                max = row[1]
                max_index = y
        else:
            break
    if max_index != -1:
        total += max
        A_sorted.pop(max_index)

print(total)





### FIXED CODE ###

from collections import defaultdict
import heapq

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

dict = defaultdict(list)
for _ in range(N):
    A, B = [int(x) for x in input().split()]
    dict[A].append(B)

h = []
total = 0
for x in range(1, M + 1):
    for y in dict[x]:
        heapq.heappush(h, -y)
    if h:
        total += heapq.heappop(h)

print(-total)
### BUGGY CODE ###

import math
n = int(input())

temp = 0

while(n > 0):
    temp += n % 10
    temp = temp % 9
    n = n // 10

if(temp % 9 == 0):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import math
n = int(input())

if(n % 9 == 0):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

#端から端まで割る
#h<=10に対しては全探索
#wについては極力割らない

h,w,k = map(int, input().split( ))

s= [list(map(int,list(input()))) for i in range(h)]

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
    if ans > tmp:
        ans = tmp
print(ans)
        












### FIXED CODE ###

    #端から端まで割る
#h<=10に対しては全探索
#wについては極力割らない

h,w,k = map(int, input().split( ))

s= [list(map(int,list(input()))) for i in range(h)]

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
            
        for u in range(1,len(cut)):###1列でもアウトな場合
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp = 100000
                white = [s[x][j] for x in range(h)]##
                break##    
    if ans > tmp:
        ans = tmp
print(ans)