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

h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v.append('-')
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)


### FIXED CODE ###

h, w = map(int, input().split())
S = [input() for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

import itertools
N = int(input())
S = input()

ans = set()
for v in itertools.combinations(range(N), 3):
    tmp = S[v[0]] + S[v[1]] + S[v[2]]
    ans.add(tmp)
print(len(ans))

### FIXED CODE ###

import itertools
N = int(input())
S = input()

ans = set()
for x in range(10):
    if str(x) in S:
        idx = S.index(str(x))
        for y in range(10):
            if str(y) in S[idx+1:]:
                idx2 = S[idx+1:].index(str(y)) + idx + 1
                for z in range(10):
                    if str(z) in S[idx2+1:]:
                        idx3 = S[idx2 + 1:].index(str(z)) + idx2 + 1
                        ans.add((x,y,z))
print(len(ans))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
from collections import deque
x,y,z=[],[],[]

for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])
a=x
b=y+z
a.sort(reverse=True)
b.sort()
ans=sum(a[0:N])-sum(b[0:N])
for i in range(N):
    a=x+y[0:i+1]
    b=z+y[i+1:N]
    a.sort(reverse=True)
    b.sort()
    ans=max(ans,sum(a[0:N])-sum(b[0:N]))
print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
dataX=[]
dataY=[]
mae=dict()
ushiro=dict()
N=int(input())
A=list(map(int,input().split()))
X=A[0:N]
Y=A[N:2*N]
Z=A[2*N:3*N]
for i in range(N):
    heappush(dataX,X[i])
    heappush(dataY,-1*Z[i])
mae[0]=sum(X)
ushiro[0]=-1*sum(Z)
for i in range(1,N+1):
    mae[i]=mae[i-1]+Y[i-1]
    heappush(dataX,Y[i-1])
    mae[i]-=heappop(dataX)
    ushiro[i]=ushiro[i-1]-Y[N-i]
    heappush(dataY,-1*Y[N-i])
    ushiro[i]-=heappop(dataY)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
if s < k:
    k = s

count = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if z < 0:
            break
        if z <= k:
            count += 1

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

def main():
    MOD = 998244353

    A, B, H, W = map(int, input().split())

    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[A][B] = 1

    for h in range(A, H + 1):
        for w in range(B, W + 1):
            if h == A and w == B: continue
            t = 0
            if h > A:
                t += dp[h - 1][w] * w
            if w > B:
                t += dp[h][w - 1] * h
            if h > A and w > B:
                t -= dp[h - 1][w - 1] * (h - 1) * (w - 1)
            dp[h][w] = t % MOD

    print(dp[H][W])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    MOD = 998244353

    A, B, H, W = map(int, input().split())

    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[A][B] = 1

    for h in range(A, H + 1):
        for w in range(B, W + 1):
            if h == A and w == B: continue
            t = 0
            if h > A:
                t += dp[h - 1][w] * w
            if w > B:
                t += dp[h][w - 1] * h
            if h > A and w > B:
                t -= dp[h - 1][w - 1] * (h - 1) * (w - 1)
            dp[h][w] = t % MOD

    print(dp[H][W])


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

s = input()
l = []
n = len(s)
dp = [[0] * 13 for i in range(n)]
mod = 1000000007
for i in range(n):
    l.append(10**i%13)
if s[-1] == "?":
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][int(s[-1])] += 1
for i in range(n-1):
    if s[n-2-i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(j*l[i+1]+k)%13] += dp[i][k]
                dp[i+1][(j*l[i+1]+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(s[n-2-i])*l[i+1]+k)%13] += dp[i][k]
            dp[i+1][(int(s[n-2-i])*l[i+1]+k)%13] %= mod
print(dp[-1][5])

### FIXED CODE ###

s = input()
l = []
n = len(s)
dp = [[0] * 13 for i in range(n)]
mod = 1000000007
for i in range(n):
    l.append(pow(10, i, 13))
if s[-1] == "?":
    for i in range(10):
        dp[0][i] += 1
else:
    dp[0][int(s[-1])] += 1
for i in range(n-1):
    if s[n-2-i] == "?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(j*l[i+1]+k)%13] += dp[i][k]
                dp[i+1][(j*l[i+1]+k)%13] %= mod
    else:
        for k in range(13):
            dp[i+1][(int(s[n-2-i])*l[i+1]+k)%13] += dp[i][k]
            dp[i+1][(int(s[n-2-i])*l[i+1]+k)%13] %= mod
print(dp[-1][5])
### BUGGY CODE ###

(N,K,Q) = map(int,list(input().split()))
points = []
for x in range(0,N):
    points.append(K)
for y in range(0,Q):
    seikaisha = int(input()) - 1
    for z in range(0,N):
            if z == seikaisha:
                continue
            else:
                points[z] -= 1        
for point in points:
    if point > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

points = []
for x in range(N):
    points.append(K-Q)

for y in range(Q):
    ansed = int(input()) - 1
    points[ansed] += 1

for point in points:
    if point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from sys import stdin
S = input()
x = S
y =str()   
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            x += Q[i][2]#先頭
        else :
            y += Q[i][2]
M = "".join([y[::-1],x])
if flag == True:
    print(M)
else:
    print(M[::-1])  

### FIXED CODE ###

from sys import stdin
S = input()
x = S
y =str()   
N = int(input())
Q =  [list(map(str, stdin.readline().split())) for _ in range(N)]
flag = True
for i in range(N):
    if Q[i][0]=="1":
        flag = not(flag)                
    else: 
        if (Q[i][1] == "2") == (flag == True):
            x += Q[i][2]#先頭
        else :
            y += Q[i][2]
M = "".join([y[::-1],x])
if flag == True:
    print(M)
else:
    print(M[::-1])
### BUGGY CODE ###

# coding: utf-8
from collections import defaultdict, deque


def solve(*args: str) -> str:
    n = int(args[0])
    x = int(args[1], 2)

    ret = []
    dp = defaultdict(int)
    for i in range(n):
        m = x ^ (1 << (n-i-1))
        count = 0
        deq = deque()
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % bin(m).count('1')
            count += 1
        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1
    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    xor_set = 1 % (x_count+1)
    if 1 < x_count:
        x_mod_reset = x_dec % (x_count-1)
        xor_reset = 1 % (x_count-1)

    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(str(0))
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        if 1 < x_count:
            xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import math

def pri_num(n):
    for i in range(2,math.floor(n**0.5)+1):
        if n%i == 0:
            return 0
    return 1

def like_2017(n1):
    f2 = pri_num((n1+1)//2)
    if f2 == 0:
        return 0
    f1 = pri_num(n1)
    return f1*f2

Q = int(input())
memo = [-1]*(10**5+1)
for _ in range(Q):
    l,r= map(int,input().split())
    cnt = 0
    for i in range(l,r+1,2):
        if i == 1:
            continue
        else:
            if memo[i] == -1:
                memo[i]= like_2017(i)
            cnt += memo[i]
    print(cnt)
    


### FIXED CODE ###

memo =[1]*(10**5+1)
memo[0]=0
memo[1]=0
for i in range(2,len(memo)):
    if memo[i]==0:
        continue
    else:
        for j in range(i*2,len(memo),i):
            memo[j]=0
memo_like2017 = [0]*(10**5+1)
for i in range(3,len(memo),2):
    if memo[i]==1 and memo[(i+1)//2] ==1:
        memo_like2017[i]=1
sum_memo=[0]*(10**5+1)
for i in range(1,len(memo)):
    sum_memo[i] = sum_memo[i-1]+memo_like2017[i]

Q = int(input())
for _ in range(Q):
    l,r = map(int,input().split())
    print(sum_memo[r]-sum_memo[l-1])
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**7)
N, Q = [int(x) for x in input().split()]
to = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x)-1 for x in input().split()]
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    ans[p] += x

def dfs(v, p=-1):
    for u in to[v]:
        if (u == p): continue
        ans[u] += ans[v]
        dfs(u, v)        
dfs(0)
print(' '.join([str(i) for i in ans]))


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
to = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x)-1 for x in input().split()]
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    ans[p] += x

from collections import deque
q = deque()
q.append(0)
visited = [0] * N

while(q):
    v = q.pop()
    visited[v] = 1    
    for u in to[v]:
        if visited[u] == 1: continue
        ans[u] += ans[v]
        q.append(u)
print(' '.join([str(i) for i in ans]))
### BUGGY CODE ###

import copy
H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
#######
p,q = [],[]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            p.append([h-1,w])
            p.append([h+1,w])
            p.append([h,w-1])
            p.append([h,w+1])
ans = 0
while True:
    q = copy.copy(p)
    p.clear()
    while len(q)!=0:
        h,w = q[0][0],q[0][1]
        del q[0]
        if h<0 or h>=H or w<0 or w>=W or A[h][w]=="#":
            continue
        A[h][w] = "#"
        p.append([h-1,w])
        p.append([h+1,w])
        p.append([h,w-1])
        p.append([h,w+1])
    if p==[]:
        break
    ans+=1
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
A = [list(input()) for i in range(H)]
S = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w]=="#":
            S[h][w] = H*W
for h in range(H):
    a = 0
    for w in range(W):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for w in range(W)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
for w in range(W):
    a = 0
    for h in range(H):
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
    for h in range(H)[::-1]:
        S[h][w] = max(a,S[h][w])
        a = max(a,S[h][w])-1
ans = H*W
for h in range(H):
    for w in range(W):
        ans = min(ans,S[h][w])
print(H*W-ans)
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    adj = [[] for i in range(N + 1)]
    for i in range(N - 1):
        A, B = map(int, f_i.readline().split())
        adj[A].append(B)
        adj[B].append(A)
    
    mod = 10 ** 9 + 7
    pow2 = [(2 ** i) % mod for i in range(N + 1)]
    
    from sys import setrecursionlimit
    setrecursionlimit(10 ** 6)
    
    ans = 0
    def dfs(node, parent):
        nonlocal ans
        cnt = 1
        for child in adj[node]:
            if child != parent:
                cnt += dfs(child, node)
        
        ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
        ans %= mod
        return cnt
    
    dfs(1, None)
    
    ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
    ans = ans * pow(pow2[N], mod - 2, mod) % mod
    
    print(ans)

solve()

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
ans=1
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)

for i in range(1,len(s)):
    if s[i]=="?":
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
    else:
        for j in range(13):
            cnt[i][(j*10+int(s[i]))%13]+=cnt[i-1][j]

# print(cnt)
print(cnt[len(s)-1][5]%mod)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
s=input()
mod=10**9+7
cnt=[[0]*13 for i in range(len(s))]
if s[0]=="?":
    for i in range(10):  
        cnt[0][i]+=1
else:
    cnt[0][int(s[0])]+=1
# print(cnt)
n=len(s)
for i in range(1,n):
    if s[i]=="?":
        now=-1
    else:
        now=int(s[i])
    if now==-1:
        for j in range(13):
            for k in range(10):
                cnt[i][(j*10+k)%13]+=cnt[i-1][j]
                cnt[i][(j*10+k)%13]%=mod
    else:
        for j in range(13):
            cnt[i][(j*10+now)%13]+=cnt[i-1][j]
            cnt[i][(j*10+now)%13]%=mod

# print(cnt)
print(cnt[n-1][5]%mod)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def main():
    n = I()
    V = []
    W = []
    for _ in range(n):
        v, w = LI()
        V.append(v)
        W.append(w)
    
    q = I()
    vl = []
    maxL = 0
    for _ in range(q):
        v, l = LI()
        maxL = max(maxL, l)
        vl.append([v,l])
    
    m = min(n, 1 << 11)
    dp = [[0]*(maxL + 1) for _ in range(m + 1)]
    
    for i in range(1, m+1):
        v, w = V[i-1], W[i-1]
        for j in range(maxL+1):
            if j < w:
                dp[i][j] = dp[i>>1][j]
            else:
                dp[i][j] = max(dp[i>>1][j], dp[i>>1][j - w] + v)
    
    
    for i in range(q):
        v, L = vl[i]
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        tmp = v
        while tmp > m:
            tmp >>= 1
            cnt += 1
        ret = 0
        for j in range(1 << cnt):
            weight_sum = 0
            value_sum = 0
            tmp = v
            idx = j
            while tmp > m:
                if idx & 1:
                    weight_sum += W[tmp - 1]
                    if weight_sum > L:
                        break
                    value_sum += V[tmp - 1]
                tmp >>= 1
                idx >>= 1
            else:
                value_sum += dp[tmp][L - weight_sum]
                ret = max(ret, value_sum)
        print(ret)
    return

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

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

import sys

readline = sys.stdin.readline
s = list(readline().strip())
n = int(readline())
q = sys.stdin.readlines()
reverse = False
for qi in q:
    if qi[0] == '1':
        reverse = not reverse
    else:
        c = qi[4]
        if qi[2] == '2':
            if reverse:
                s = [c] + s
            else:
                s.append(c)
        else:
            if reverse:
                s.append(c)
            else:
                s = [c] + s
if reverse:
    s = reversed(s)
print(''.join(s))


### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline
s = deque(readline().strip())
n = int(readline())
q = sys.stdin.readlines()
reverse = False
for qi in q:
    if qi[0] == '1':
        reverse = not reverse
    else:
        c = qi[4]
        if qi[2] == '2':
            if reverse:
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if reverse:
                s.append(c)
            else:
                s.appendleft(c)
if reverse:
    s = reversed(list(s))
print(''.join(s))
### BUGGY CODE ###

h,w,K=map(int,input().split())
s=[list(input()) for i in range(h)]
from itertools import groupby
ans=10**18
for i in range(1<<h):
  pre=-1
  c=[]
  t_cnt=0
  op=[-1]*h
  for j in range(h):
    if i&(1<<j):op[j]=1
    else:op[j]=0
  gr=groupby(op)
  l=[]
  for key,g in gr:
    l.append(len(list(g)))
  c=[[0]*w for _ in range(len(l))]
  idx=0
  jdx=0
  for idx,li in enumerate(l):
    for k in range(li):
      for a in range(w):
        c[idx][a]+=int(s[jdx][a])
      jdx+=1
  t_cnt=len(c)-1
  t_cnt1=0
  c_mx=[0]*len(c)
  for a in range(w):
    for b in range(len(c)):
      c_mx[b]+=c[b][a]
      if c_mx[b]>K:
        t_cnt1+=1
        c_mx=[0]*len(c)
        for b in range(len(c)):
          c_mx[b]+=c[b][a]
        break
  ans=min(ans,t_cnt+t_cnt1)
print(ans)


### FIXED CODE ###

h,w,K=map(int,input().split())
s=[list(input()) for i in range(h)]
from itertools import groupby
ans=10**18
for i in range(1<<h):
  pre=-1
  c=[]
  t_cnt=0
  op=[-1]*h
  for j in range(h):
    if i&(1<<j):op[j]=1
    else:op[j]=0
  gr=groupby(op)
  l=[]
  for key,g in gr:
    l.append(len(list(g)))
  c=[[0]*w for _ in range(len(l))]
  idx=0
  jdx=0
  for idx,li in enumerate(l):
    for k in range(li):
      for a in range(w):
        c[idx][a]+=int(s[jdx][a])
      jdx+=1
  # print(c)
  t_cnt=len(c)-1
  t_cnt1=0
  c_mx=[0]*len(c)
  ok=True
  for a in range(w):
    for b in range(len(c)):
      if c[b][a]>K:
        ok=False
      c_mx[b]+=c[b][a]
      if c_mx[b]>K:
        t_cnt1+=1
        c_mx=[0]*len(c)
        for b in range(len(c)):
          c_mx[b]+=c[b][a]
        break
  if ok:
    ans=min(ans,t_cnt+t_cnt1)
if ans==10**18:
  print(0)
else:
  print(ans)
### BUGGY CODE ###

K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
work_lists = [[0] * 13 for i in range(6)]
for i in range(6):
    for x in range(10):
        work_lists[i][(x * (10 ** i)) % 13] = 1
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = work_lists[i % 6]
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) % K for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** (i % 6))) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = next_li
print(li[5])


### FIXED CODE ###

K = 1000000007
S = input()
l = len(S)
li = [1] + [0] * 12
work_lists = [[0] * 13 for i in range(6)]
for i in range(6):
    for x in range(10):
        work_lists[i][(x * (10 ** i)) % 13] = 1
for i in range(l):
    s = S[l - i - 1]
    if s == "?":
        work_li = work_lists[i % 6]
        next_li = [sum([work_li[j] * li[(k - j) % 13] for j in range(13)]) % K for k in range(13)]
    else:
        n = int(s)
        r = (n * (10 ** (i % 6))) % 13
        next_li = [li[(j - r) % 13] for j in range(13)]
    li = next_li
print(li[5])