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

# input
N = int(input())

# check
all_case = [
    sum((i - 1, j - 1))
    for i in range(1, N + 1, 1)
    for j in range(1, N + 1, 1)
    if i * j == N
]

print(min(all_case))

### FIXED CODE ###

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


# input
N = int(input())

# div = divisors(N)
div = get_div(N)
mov = []
append = mov.append
for x in div:
    y = N // x
    append(sum([x - 1, y - 1]))

print(min(mov))

# check
cnt = 0
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]

visited = [[float('inf')] * W for i in range(H)]

def bfs():
    queue = deque()
    for i in range(H):
      for j in range(W):
        if A[i][j] == '#':
            queue.append([i,j])
            visited[i][j] = 0

    while queue:
        y,x = queue.popleft()
    
        for i in range(4):
            nx = x + dy[i]
            ny = y + dx[i]
    
            if 0 <= ny < H and 0 <= nx < W and visited[ny][nx] == float('inf'):
                queue.append([ny,nx])
                visited[ny][nx] = visited[y][x] + 1
    
    tmp = 0
    for k in range(H):
        if tmp < max(visited[k]):
            tmp = max(visited[k])
    
    return tmp

print(bfs())
            


### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(4100000)
def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    Q = deque([])
    visited = [[float('inf')] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                Q.append((h,w))
                visited[h][w] = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    ans = 0
    while Q:
        y, x = Q.popleft()
        now = visited[y][x]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == float('inf'):
                    visited[ny][nx] = now + 1
                    Q.append((ny,nx))
                    ans = max(ans, now + 1)

    print(ans)




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

N = int(input())
A = list(map(int,input().split()))
mod = 1000000000 + 7
add = 0
for i in range(N):
    tmp = sum(A[i+1:N])
    add += tmp * A[i]
print(add%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 1000000000 + 7
add = 0
tmp = sum(A)
for i in range(N):
    tmp -= A[i]
    add += tmp * A[i]
print(add%mod)
### BUGGY CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))

cnt_list = [int_list.count(i) for i in range(1, N+1)]
ret_list = []

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] < 2:
        continue
    else:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2

# for i in range(N):
#     if cnt_list[i] < 1:
#         tmp_ret = 0
#     else:
#         tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
#     ret_list.append(tmp_ret)

# for i in int_list:
#     print(ret_list[i-1])

ret_list = [0 if cnt_list[i] < 1 else tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2 for i in range(N)]

[print(ret_list[i-1]) for i in int_list]

### FIXED CODE ###

from sys import stdin

N = stdin.readline().rstrip().split()
N = int(N[0])

int_list = list(map(int, stdin.readline().rstrip().split()))
cnt_list = [0] * N

for i in int_list:
    cnt_list[i-1] += 1

ret_list = [0] * N

# これはO(N)でいける

tmp_ans = 0
for i in range(N):
    if cnt_list[i] > 1:
        tmp_ans += cnt_list[i]*(cnt_list[i]-1) // 2


for i in range(N):
    if cnt_list[i] < 1:
        tmp_ret = 0
    else:
        tmp_ret = tmp_ans - cnt_list[i]*(cnt_list[i]-1) // 2 + (cnt_list[i]-1)*(cnt_list[i]-2) // 2
    ret_list[i] = tmp_ret

for i in int_list:
    print(ret_list[i-1])
### BUGGY CODE ###

n,m = map(int, input().split())
H = list(map(int, input().split()))
a=[]
for _ in range(m):
    a.append(list(map(int,input().split())))

ans=n

for i in range(1,n+1):
    for j in range(m):
        k=a[j][0]
        l=a[j][1]
        if i==k or i==l:
            if i==k:
                if H[k-1]<=H[l-1]:
                    ans-=1
                    break
            else:
                if H[l-1]<=H[k-1]:
                    ans-=1
                    break
        else:
            continue

print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
h = list(map(int, input().split()))
tmp=[0]*n
for _ in range(m):
    a,b=map(int, input().split())
    tmp[a-1]=max(tmp[a-1],h[b-1])
    tmp[b-1]=max(tmp[b-1],h[a-1])
ans=0
for i in range(n):
    if h[i]>tmp[i]:
        ans+=1

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

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort()
#dp = [[0 for _ in range(X+1)] for _ in range(N+1)]
#dp = [[0] * (X+1) for _ in range(N+1)]

#dp[0] = [x for x in range(X+1)]
from collections import defaultdict
dp = defaultdict(lambda: defaultdict(int))
for x in range(X+1):
    dp[0][x] = x


for i, n  in enumerate(numbers):
    for x in range(X+1):
        dp[i+1][x] += dp[i][x % n]
        #dp[i+1][x] = dp[i+1][x] % MOD
        
        dp[i+1][x] += dp[i][x] * i #% MOD
        #dp[i+1][x] = dp[i+1][x] % MOD

print(dp[N][X] % MOD)


### FIXED CODE ###

N, X = map(int, input().split())
S = list(map(int, input().split()))

MOD = 1000000007
numbers = S[:]
numbers.sort(reverse=True)


dp = {X: 1}

for i, n in enumerate(numbers):
    tmp_dp = {}
    for k, v in dp.items():
        if k < n:
            tmp_dp[k] = (tmp_dp.get(k,0)+v*(N-i))
        else:
            tmp_dp[k]=(tmp_dp.get(k,0)+v*(N-i-1)) 
            tmp_dp[k%n]=(tmp_dp.get(k%n,0)+v) 
    dp = tmp_dp.copy()
        
ans = 0
for k, v in dp.items():
    ans += k *  v

print(ans % MOD)
### BUGGY CODE ###

N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
ans = 0
for i in set(s):
    n = s.count(i)
    ans += n * (n - 1) // 2
print(ans)


### FIXED CODE ###

import collections
 
N = int(input())
s = ["".join(sorted(input())) for _ in range(N)]
c = collections.Counter(s)
ans = 0
for si in set(s):
    n = c[si]
    ans += n * (n - 1) // 2
print(ans)
### BUGGY CODE ###

def mergeSort(num_list, left, right):
	if left + 1 < right:
		mid = (left + right) / 2
		mergeSort(num_list, left, mid)
		mergeSort(num_list, mid, right)
		merge(num_list, left, mid, right)

def merge(num_list, left, mid, right):
	global count 
	L = []
	R = []
	for i in range(	mid - left):
		L.append(int(num_list[left + i]))
	L.append(float("inf"))
	for i in range(	right - mid):
		R.append(int(num_list[mid + i]))
	R.append(float("inf"))
	i, j = 0, 0
	for k in range(left, right):
		if L[i] <= R[j]:
			num_list[k] = L[i]
			i += 1
			count += 1
		else:
			num_list[k] = R[j]
			j += 1
			count += 1

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
mergeSort(l, 0, n)

print " ".join(map(str, l)) 
print count

### FIXED CODE ###

def mergeSort(num_list, left, right):
	if left + 1 < right:
		mid = (left + right) / 2
		mergeSort(num_list, left, mid)
		mergeSort(num_list, mid, right)
		merge(num_list, left, mid, right)

def merge(num_list, left, mid, right):
	global count 
	L = list(num_list[left:mid])
	L.append(float("inf"))
	R = list(num_list[mid:right])
	R.append(float("inf"))
	i, j = 0, 0
	for k in range(left, right):
		if L[i] <= R[j]:
			num_list[k] = L[i]
			i += 1
			count += 1
		else:
			num_list[k] = R[j]
			j += 1
			count += 1

count = 0
n = int(raw_input())
a = raw_input()
l = []
l = a.split(" ")
for i in range(len(l)):
	l[i] = int(l[i])
mergeSort(l, 0, n)

print " ".join(map(str, l)) 
print count
### BUGGY CODE ###

import queue
n,q = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in range(n-1)])
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
tree = [set() for i in range(n)]
branch = queue.Queue()
check = [0]*n
check[0] = 1
for l in ab:
    branch.put(l)
while not branch.empty():
    a,b = branch.get()
    if check[a-1] == 0 & check[b-1] == 0:
        branch.put([a,b])
        continue
    elif check[a-1] == 1:
        tree[a-1].add(b-1)
        check[b-1] = 1
    else:
        tree[b-1].add(a-1)
        check[a-1] = 1   
    
q = queue.Queue()
q.put(0)
while not q.empty():
    num = q.get()
    for k in tree[num]:
        count[k] += count[num]
        q.put(k)
        
print(*count)

### FIXED CODE ###

n,q = map(int,input().split())
tree = [set() for _ in range(n)]
for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].add(b-1)
    tree[b-1].add(a-1)
count = [0]*n
for _ in range(q):
    p,x = map(int,input().split())
    count[p-1] += x
    
stack = [[0,0,-1]] # [number,count,pair]
while stack:
    num,cnt,pr = stack.pop()
    count[num] += cnt
    for k in tree[num]:
        if k == pr:
            continue
        stack.append([k,count[num],num])
        
print(*count)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
t = [0]*(N+1)
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        t[i+1] = 1

for _ in range(Q):
    l=list(map(int,input().split()))
    print(sum(t[l[0]:l[1]]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t = [0]*(N+1)
for i in range(len(S)-1):
    if S[i] == 'A' and S[i+1] == 'C':
        t[i+1] = 1

import numpy
res = numpy.cumsum(t)

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

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

N = len(S)
M = len(T)


def gcd(a, b):
    if (a < b):
        return gcd(b, a)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def maxkobai(a, b):
    return a * b // gcd(a, b)


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
#x = ['-' for i in range(L+1)]
x = {}
#x = ['-'] * (L*10)

for l in range(0, L + 1):
    x[l] = '-'


for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)


### FIXED CODE ###

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

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

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

n, *a = map(int, open(0).read().split())
for i in range(1, n + 1):
    print(a.count(i))
    a = list(filter(lambda x: x != i, a))

### FIXED CODE ###

n, *a = map(int, open(0).read().split())
bt = [None] + [0] * n

for ai in a:
    bt[ai] += 1

for a in bt[1:]:
    print(a)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
from collections import deque
q=deque(A)
 
ans=1
while len(q)>0:
    p=q.popleft()
    ans=ans*p
if ans>1000000000000000000:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

ans=1

if 0 in A:
    print(0)
    exit()

for i in A:
   ans=ans*i
   if ans>10**18:
    print(-1)
    exit()


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

def main():
    H, W = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(H+1)]
    dp[1][1].add(abs(A[0][0] - B[0][0]))
    for i in range(H):
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            dp[i+1][j+1] |= set(map(lambda x: abs(x + diff), dp[i][j+1]))
            dp[i+1][j+1] |= set(map(lambda x: abs(x - diff), dp[i][j+1]))
            dp[i+1][j+1] |= set(map(lambda x: abs(x + diff), dp[i+1][j]))
            dp[i+1][j+1] |= set(map(lambda x: abs(x - diff), dp[i+1][j]))
    print(min(dp[H][W]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    N = 80 * (H+W) // 2
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(2)]
    dp[0][1].add(0)
    def ltN(x): return x <= N
    for i in range(H):
        dp[(i+1) & 1] = [set() for _ in range(W+1)]
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            tmp = set()
            for x in dp[i & 1][j + 1]:
                tmp.add(abs(x + diff))
                tmp.add(abs(x - diff))
            for x in dp[(i+1) & 1][j]:
                tmp.add(abs(x + diff))
                tmp.add(abs(x - diff))
            dp[(i+1) & 1][j+1] = tmp
    print(min(dp[H & 1][W]))


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

def cal():
    x = input()
    i = 0
    while i <= 2*10**5:
        i += 1
        x = x.replace('ST', '', 10**5)
    print(len(x))

cal()


### FIXED CODE ###

x = input()
ans = []

for i in x:
    if i == 'S':
        ans.append(i)
    else:
        if len(ans) == 0 or ans[-1] == 'T':
            ans.append(i)
        else:
            ans.pop()
print(len(ans))
### BUGGY CODE ###

n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))


### FIXED CODE ###

n = int(input())
*P, = map(float, input().split())
DP = [0 for j in range(n+1)]
DP[0] = 1
for i in range(n):
    DP_ = []
    DP_.append(DP[0]*(1-P[i]))
    for j in range(1, n+1):
        DP_.append(DP[j]*(1-P[i])+DP[j-1]*P[i])
    DP = DP_
print(sum(DP[(n+1)//2:]))
### BUGGY CODE ###

import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(np.array(lr).transpose())
index_dict={}
r_dict={} 
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
    r_dict[i+1]=sorted(lr_t[1][index_dict[i+1]:])
for i in range(Q):
    p,q = map(int,input().split())
    I = index_dict[p]
    r = r_dict[p]
    I = bisect.bisect(r,q)
    print(I)

### FIXED CODE ###

import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])
### BUGGY CODE ###

import copy
n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
cnt=0
x=[]
i=0
b__=copy.copy(b)
rev=0
while(b__):
     b_=b__.pop()
     while(1):
          try:
               c_=c.pop()
          except:
               rev+=cnt
               x.append(rev)
               cnt=0
               break
          if c_>b_:
               cnt+=1
          else:
               rev+=cnt
               x.append(rev)
               cnt=0
               c.append(c_)
               break
cnt=0
i=n-1
rev=0
ans=0
while(a):
     a_=a.pop()
     while(1):
          try:
               b_=b.pop()
          except:
               rev+=cnt
               ans+=rev
               cnt=0
               break
          if b_>a_:
               cnt+=x.pop(0)
          else:
               rev+=cnt
               ans+=rev
               cnt=0
               b.append(b_)
               break
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=sorted(list(map(int,input().split())))
c=sorted(list(map(int,input().split())))
cnt=0
x=[]
i=0
b__=b.copy()
rev=0
while(b__):
     b_=b__.pop()
     while(1):
          try:
               c_=c.pop()
          except:
               rev+=cnt
               x.append(rev)
               cnt=0
               break
          if c_>b_:
               cnt+=1
          else:
               rev+=cnt
               x.append(rev)
               cnt=0
               c.append(c_)
               break
cnt=0
i=n-1
rev=0
ans=0
while(a):
     a_=a.pop()
     while(1):
          try:
               b_=b.pop()
          except:
               rev+=cnt
               ans+=rev
               cnt=0
               break
          if b_>a_:
               cnt+=x.pop(0)
          else:
               rev+=cnt
               ans+=rev
               cnt=0
               b.append(b_)
               break
print(ans)
### BUGGY CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[]
ans=0
for i in a:
  b.append(i)
  ans+=i
for k in range(1,n):
  d=0
  for i in range(n):
    b[i]=min(b[i],a[i-k])
    d+=b[i]
  ans=min(d+x*k,ans)
print(ans)

### FIXED CODE ###

n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a.copy()
ans=sum(a)
for k in range(n):
  for i in range(n):b[i]=min(b[i],a[i-k])
  ans=min(sum(b)+x*k,ans)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

result_dic = {}

for  k in range(1, N-1):
    for i in range(k):
        for j in range(k+1, N):
            result_dic[S[i] + S[k] + S[j]] = 1

print(len(result_dic))

### FIXED CODE ###

N = int(input())
S = input()

result_dic = {}

before_words = {i:0 for i in range(10)}
after_words = {i:0 for i in range(10)}
for s in S:
    after_words[int(s)] += 1

for  i, s in enumerate(S[:-1]):
    if i == 0:
        before_words[int(s)] += 1
        after_words[int(s)] -= 1
        continue
    after_words[int(s)] -= 1

    before =  [x for x, y in before_words.items() if y > 0]
    after =  [x for x, y in after_words.items() if y > 0]
    for b in before:
        for a in after:
            result_dic[str(b) + s + str(a)] = 1

    before_words[int(s)] += 1

print(len(result_dic))
### BUGGY CODE ###

import sys
from itertools import accumulate
import operator as op
input = sys.stdin.readline

n,k=map(int,input().split())
L=list(map(int,input().split()))
N=[1]+list(accumulate(L,op.mul))

ans=[]
for i in range(k,n+1):
    val = N[i]/N[i-k]
    ans.append(val)

N=len(ans)
for i in range(1,N):
    if ans[i]>ans[i-1]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans=[]
for i in range(k,n):
    if L[i]>L[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#13:27
s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i-1:i+1] == 'FF':
    raw[-1] += 1
  elif s[i-1:i+1] == 'TF':
    raw.append(1)
  if s[i-1:i+1] == 'TT':
    raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
now = [0 for _ in range(16001)]
now[8000] = 1
l = len(a)
for j in range(l):
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+a[j]] = 1
      now[i-a[j]] = 1
if now[8000+x] == 0:
  print('No')
  exit()
now = [0 for _ in range(16001)]
now[8000] = 1
l = len(b)
for j in range(l):
  last = now
  now = [0 for _ in range(16001)]
  for i in range(16001):
    if last[i] == 1:
      now[i+b[j]] = 1
      now[i-b[j]] = 1
if now[8000+y] == 1:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()
l = len(s)
s = 'F' + s
x,y = map(int,input().split())
raw = [1]
for i in range(1,l+1):
  if s[i] == 'F':
    if s[i-1] == 'F':
      raw[-1] += 1
    else:
      raw.append(1)
  if s[i] == 'T':
    if s[i-1] == 'T':
      raw.append(0)
l2 = len(raw)
a = []
b = []
for i in range(l2):
  if i == 0:
    x -= raw[i]-1
  elif i % 2 == 0:
    a.append(raw[i])
  else:
    b.append(raw[i])
#print(raw)
#print(a,x)
#print(b,y)
nowa = {0}
for aa in a:
  lasta = nowa
  nowa = set()
  for aaa in lasta:
    nowa.add(aaa+aa)
    nowa.add(aaa-aa)
nowb = {0}
for bb in b:
  lastb = nowb
  nowb = set()
  for bbb in lastb:
    nowb.add(bbb+bb)
    nowb.add(bbb-bb)
#print(nowa,nowb)
#print(x,y)
if x in nowa and y in nowb:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

# disjoint setかと思いきやDFS
# どこが悪いのかさっっっっっっぱりわからん...
# あ 再帰にしてるからその上限か
import sys

sys.setrecursionlimit(10000000)

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append([b, c])
    graph[b].append([a, c])

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, used, weight):
    for data in graph[node]:
        if data[0] not in used:
            next_used = used[:]
            next_used.append(data[0])
            dfs(data[0], next_used, weight + data[1])
    ans_list[node] = weight


dfs(k, [k], 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])


### FIXED CODE ###

# disjoint setかと思いきやDFS
# したらTLEになったので根本的にやり方が間違ってるということ
# よくよく考えたらdfsなのでそこにたどり着いたときが最短距離だわ ムダに探索してた


import sys

sys.setrecursionlimit(10000000)

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append([b, c])
    graph[b].append([a, c])

q, k = map(int, input().split())
k = k - 1
# kからスタートしてぜんぶたどる
ans_list = [0 for _ in range(n)]


def dfs(node, weight):
    for data in graph[node]:
        if not used[data[0]]:
            used[data[0]] = True
            dfs(data[0], weight + data[1])
    ans_list[node] = weight


used = [False for _ in range(n)]
used[k] = True
dfs(k, 0)

for _ in range(q):
    a, b = map(lambda x: int(x) - 1, input().split())
    print(ans_list[a] + ans_list[b])
### BUGGY CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
      else:
        l = y
    ans = min(ans,t_a)

  print(ans)
  
main()

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

  print(ans)
  
main()