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

import math
n, m = map(int, input().split())
k = math.floor(m / n)
for kk in range(k, 0, -1):
    if m % kk == 0:
        ans = kk
        break
print(ans)

### FIXED CODE ###

import math
a_list = []
n, m = map(int, input().split())
for i in range(math.ceil(m**(1/2)), 0, -1):
    if m % i == 0:
        a_list.append(i)
        a_list.append(m//i)
border = math.floor(m / n)
a_list = list(reversed(sorted(a_list)))
for aa in a_list:
    if border >= aa:
        ans = aa
        break
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

for i in range(N):
    for j in range(N-i-A[i]):
        k=i+j+A[i]
        if A[i]+A[k]==abs(i-k):
            count = count+1
            #print("{} {}".format(i+1,k+1))



print("{}".format(count))


### FIXED CODE ###

# -*- coding: utf-8 -*-

N = int(input())
A = list(map(int, input().split()))
count=0
L = [0]*N
R = [0]*N
N2=2*N
hash_L=[0]*N2
hash_R=[0]*N2

sheet_L=[0]*N2
sheet_R=[0]*N2
for i in range(N):
    L[i]=A[i]+i+1
    if L[i]<N2:
        if sheet_L[L[i]]==0:
            hash_L[L[i]]=L[i]
            sheet_L[L[i]]=1
        else:
            sheet_L[L[i]]=sheet_L[L[i]]+1

    R[i]=-A[i]+i+1
    if R[i]>0:
        if sheet_R[R[i]]==0:
            hash_R[R[i]]=R[i]
            sheet_R[R[i]]=1
        else:
            sheet_R[R[i]]=sheet_R[R[i]]+1


for i in range(2*N):
    if not hash_L[i]==0:
        if hash_L[i]==hash_R[i]:
            count=count+sheet_L[i]*sheet_R[i]
#print("{}".format(hash_L))
#print("{}".format(hash_R))
print("{}".format(count))
### BUGGY CODE ###

import fractions
import math
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9 + 7
ans = 0

lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])
    #lcm = lcm * a[i] // math.gcd(lcm, a[i])
a2 = list(map(lambda x: lcm//x % MOD, a))
print(sum(a2)%MOD)
#
#
#
# for i in range(n):
#     ans += (lcm // a[i]) % MOD
#     ans %= MOD

#print(ans)


### FIXED CODE ###

import fractions
import math
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9 + 7
ans = 0

lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])
    #lcm = lcm * a[i] // math.gcd(lcm, a[i])
lcm %= MOD
for i in range(n):
    ans += lcm * pow(a[i] , MOD-2, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
A = [int(i) for i in input().split(maxsplit=N)]
sumA = 0
for a, b in combinations(A, 2):
    sumA += (a * b) % (10**9 + 7)
print(sumA % (10**9 + 7))


### FIXED CODE ###

def resolve():
    N = int(input())
    A = [int(i) for i in input().split(maxsplit=N)]
    presum = [0 for _ in range(N + 1)]
    for i in range(N):
        presum[i + 1] = presum[i] + A[i]
    sumA = 0
    for i in range(1, N):
        sumA += (A[i] * (presum[i])) % (10**9 + 7)
    print(sumA % (10**9 + 7))


resolve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

cnt = 0
for i in range(n):
  a = l[i]
  for j, b in enumerate(l[i+1:]):
    for c in l[i+j+2:]:
      if (a < b+c) and (b < a+c) and (c <  a+b):
        cnt += 1
        
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    cnt += bisect.bisect_left(l, l[i]+l[j])-j-1
    
print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()

ans = set()
for i in range(n):
  for j in range(i+1, n):
    for k in range(j+1, n):
      a, b, c = int(s[i]), int(s[j]), int(s[k])
      ans.add(100*a+10*b+c)
print(len(ans))   

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for a in range(10):
  for b in range(10):
    for c in range(10):
      a, b, c = str(a), str(b), str(c)
      a_find = s.find(a)
      if a_find == -1:
        continue
      b_find = s.find(b, a_find + 1)
      if b_find == -1:
        continue
      c_find = s.find(c, b_find + 1)
      if c_find == -1:
        continue
      ans += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    return N, A, B, C


def binary_search(l: list, key: int) -> int:
    """
    l[index] > keyとなる最小のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] > keyとなる最小のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess > key:
            high = mid
        else:
            low = mid
    return high


def main(N: int, A: list, B: list, C: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): パーツの数
        A (list): 上部のパーツのサイズ
        B (list): 中部のパーツのサイズ
        C (list): 下部のパーツのサイズ
    """
    # 事前にリストをソートしておく
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)

    # 求解処理
    ans = 0
    for i in range(N):
        A_i = A[i]
        lb_B = binary_search(B, A_i)
        for j in range(lb_B, N):
            B_j = B[j]
            lb_C = binary_search(C, B_j)
            ans += N - lb_C

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A, B, C = get_input()

    # メイン処理
    main(N, A, B, C)


### FIXED CODE ###

# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    return N, A, B, C


def get_lb(l: list, key: int) -> int:
    """
    l[index] > keyとなる最小のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] > keyとなる最小のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess > key:
            high = mid
        else:
            low = mid
    return high


def get_ub(l: list, key: int) -> int:
    """
    l[index] < keyとなる最大のindexを求める.

    Args:\n
        l (list): リスト
        key (int): 整数

    Returns:\n
        int: l[index] < keyとなる最大のindex
    """
    low = -1
    high = len(l)
    while 1 < high - low:
        mid = (low + high) // 2
        guess = l[mid]
        if guess < key:
            low = mid
        else:
            high = mid
    return low


def main(N: int, A: list, B: list, C: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): パーツの数
        A (list): 上部のパーツのサイズ
        B (list): 中部のパーツのサイズ
        C (list): 下部のパーツのサイズ
    """
    # 事前にリストをソートしておく
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)

    # 求解処理
    ans = 0
    for i in range(N):
        B_i = B[i]
        ans += (get_ub(A, B_i) + 1) * (N - get_lb(C, B_i))

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, A, B, C = get_input()

    # メイン処理
    main(N, A, B, C)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    q = list(map(str, input().split()))
    if len(q)==1:
        S = ''.join(reversed(list(S)))
    else:
        if q[1]=='1':
            S = ''.join([q[2], S])
        else:
            S = ''.join([S, q[2]])

print(S)

### FIXED CODE ###

S = input()
Q = int(input())
hanten = 1
front = []
back = []
for _ in range(Q):
    q = list(map(str, input().split()))
    if q[0]=='1':
        hanten *= -1
    else:
        if hanten==1:
            if q[1]=='1':
                front.append(q[2])
            else:
                back.append(q[2])
        else:
            if q[1]=='1':
                back.append(q[2])
            else:
                front.append(q[2])


if hanten==1:
    print(''.join(list(reversed(front)) + list(S) + back))
else:
    print(''.join(list(reversed(list(S)+back))+front))
### BUGGY CODE ###

import math
n = int(input())
a = [int(i) for i in input().split()]

a.sort()
b = set()
c = 0
for i, v in enumerate(a):
    flag = True
    for j in range(1, int(math.sqrt(v))+1):
        if v % j == 0 and (j in b or v/j in b):
            flag = False
            break
    if flag == True:
        b.add(v)
        if i+1 >= len(a):
            c += 1
        elif a[i+1] != v:
            c += 1
  
print(c)

### FIXED CODE ###

import math
n = int(input())
a = [int(i) for i in input().split()]

a.sort()
b = [0 for _ in range(a[-1])]
c = 0
for i in a:
    x = i-1
    while len(b) > x:
        b[x] += 1
        x += i 
for i in a:
    if b[i-1] == 1:
        c += 1
print(c)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
import sys


n,k = map(int, sys.stdin.readline().rstrip().split())
h = [0] + list(map(int, sys.stdin.readline().rstrip().split()))

dp = [sys.maxsize] * (n+k+1)
dp[0], dp[1] = [0, 0]
for i in range(1,n+1):
  for j in range(1,k+1):
    if i+j < len(h):
      dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

print(dp[n])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
import sys
import numpy as np

n,k = map(int, sys.stdin.readline().rstrip().split())
h = np.array(list(map(int, sys.stdin.readline().rstrip().split())))

dp = np.zeros(n, dtype=np.int)

for i in range(1,n):
  if i < k:
    dp[i] = np.min(dp[:i] + np.abs(h[i]-h[:i]))
  else:
    dp[i] = np.min(dp[i-k:i] + np.abs(h[i]-h[i-k:i]))

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

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

for i in range(N):
	Xi = list(X)
	Xi.pop(i)
	Xi.sort()
	Xi.reverse()
	num = int((len(Xi)-1)/2)
	print(Xi[num])

### FIXED CODE ###

N = int(input())
x = input().split()
X = list(map(int,x))
Xi = list(X)
Xi.sort()
Xi.reverse()


for i in range(N):
	if(X[i]<Xi[int(N/2)-1]):
		print(Xi[int(N/2)-1])
	elif(X[i]>=Xi[int(N/2)-1]):
		print(Xi[int(N/2)])
### BUGGY CODE ###

import bisect
n = int(input())
c = []
for i in range(n):
    a = int(input())
    idx = bisect.bisect_left(c,a)
    if idx == 0:
        c.insert(idx, a)
    else:
        c[idx-1] = a
print(len(c))

### FIXED CODE ###

import bisect
from collections import deque
n = int(input())
c = deque()
for i in range(n):
    a = int(input())
    idx = bisect.bisect_left(c,a)
    if idx == 0:
        c.appendleft(a)
    else:
        c[idx-1] = a
print(len(c))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
Q = int(input())

def isPrime(n):
    if n == 1:
        return False
    if n == 2:
        return True
    if n%2 == 0:
        return False
    for i in range(3, math.ceil(math.sqrt(n))+1, 1):
        if n % i == 0:
            return False
    return True

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0
    for i in range(l, r+1, 2):
        if isPrime(i) and isPrime((i+1)/2):
            #print(l,r,i)
            num += 1
    print(num)



### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
Q = int(input())

ls = []
rs = []
for n in range(Q):
    l, r = map(int, input().split())
    ls.append(l)
    rs.append(r)
    num = 0

max_r = max(rs)

def eratos(n):
    if n == 1:
        return set()
    primes = [1 for i in range(n+1)]
    primes[0] = 0
    primes[1] = 0
    for i in range(2,math.floor(math.sqrt(n))+1):
        if primes[i] == 1:
            j = i + i
            while j <= n:
                primes[j] = 0
                j = j + i
    return primes


def count_similar(era, n):
    count_similar = [0 for i in range(n+1)]
    for i in range(1,n+1):
        count_similar[i] = count_similar[i-1]
        if era[i] == 1 and era[int((i+1)/2)] == 1:
            count_similar[i] += 1
    return count_similar




era = eratos(max_r)
cnt = count_similar(era, max_r)

for l, r in zip(ls, rs):
    print(cnt[r] - cnt[l-1])
### BUGGY CODE ###

def bell(edges, n):
    dist = [0 for i in range(n)]
 
    changed = True
 
    while changed:
        changed = False
        for edge in edges:
            if dist[edge[1]] < dist[edge[0]] + 1:
                changed = True
                dist[edge[1]] = max(dist[edge[0]] + 1, dist[edge[1]])
                
    return dist
 
 
n,m = map(int,input().split())
edges = []
for _ in range(m):
    a, b= (int(x) for x in input().split())
    edges.append([a-1, b-1])
 
res = bell(edges, n)
print(max(res))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
 
n, m = map(int, input().split())
 
edges = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    edges[x].append(y)
 
dp = [-1 for _ in range(n+1)]
 
def longest_path(u):
    if dp[u] != -1:
        return dp[u]
    d = 0
    for v in edges[u]:
        d = max(d, 1+longest_path(v))
    dp[u] = d
    return d
 
for u in range(1, n+1):
    longest_path(u)
 
print(max(dp))
### BUGGY CODE ###

N, K = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]

ans = 10 ** 19
for a in range(N):
    for b in range(a+1, N):
        for c in range(N):
            for d in range(c+1, N):
                x0 = data[a][0]
                x1 = data[b][0]
                y0 = data[c][1]
                y1 = data[d][1]

                if x0 > x1:
                    x0, x1 = x1, x0
                if y0 > y1:
                    y0, y1 = y1, y0

                count = 0
                for i, j in data:
                    if x0 <= i <= x1 and y0 <= j <= y1:
                        count += 1
                if count >= K:
                    ans = min(ans, (x1 - x0)*(y1 - y0))

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(N)]

ans = 10 ** 19
for a in range(N):
    for b in range(a+1, N):
        for c in range(N):
            for d in range(c+1, N):
                x0 = data[a][0]
                x1 = data[b][0]
                y0 = data[c][1]
                y1 = data[d][1]

                if x0 > x1:
                    x0, x1 = x1, x0
                if y0 > y1:
                    y0, y1 = y1, y0

                count = 0
                for i, j in data:
                    if x0 <= i <= x1 and y0 <= j <= y1:
                        count += 1
                if count >= K:
                    ans = min(ans, (x1 - x0)*(y1 - y0))

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

import math
from functools import reduce

K = int(input())

sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            sum += reduce(math.gcd, [a, b, c])

print(sum)


### FIXED CODE ###

import math
from functools import reduce

K = int(input())
sum = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        AB_gcd = math.gcd(a, b)
        for c in range(1, K+1):
            sum += math.gcd(AB_gcd, c)

print(sum)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix
import sys
input = sys.stdin.readline

n = int(input())
A = []
B = []
C = []

for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    A.append(a-1)
    B.append(b-1)
    C.append(c)

q, k = map(int, input().split())
k -= 1

d = dijkstra(csr_matrix((C, (A, B)), shape = (n, n)), directed=False, indices=k).astype(int)

for j in range(q):
    x, y = map(int, input().split())
    print(d[x-1] + d[y-1])




### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline

INF = 10 ** 18

class Edge():
    def __init__(self, start, end, cost):
        self.start = start
        self.end = end
        self.cost = cost
    def __str__(self):
        return 'Edge: {} -> {}, cost {}'.format(self.start, self.end, self.cost)

def dijkstra(n, G, s):
    dist = [INF] * n
    dist[s] = 0
    h = []
    heapq.heappush(h, (0, s))

    while h:
        # 使っていない頂点のうち、現時点で最も距離の近いものを選びvとする
        d, v = heapq.heappop(h)
        if dist[v] < d:
            continue
        # vから到達可能な頂点について、距離が短くなれば更新
        for e in G[v]:
            if dist[e.end] > dist[v] + e.cost:
                dist[e.end] = dist[v] + e.cost
                heapq.heappush(h, (dist[e.end], e.end))
    return dist


n = int(input())
es = [[] for i in range(n)]

for i in range(n-1):
    a, b, c = list(map(int, input().split()))
    es[a-1].append(Edge(a-1, b-1, c))
    es[b-1].append(Edge(b-1, a-1, c))

q, k = map(int, input().split())
k -= 1

d = dijkstra(n, es, k)

for j in range(q):
    x, y = map(int, input().split())
    print(d[x-1] + d[y-1])
### BUGGY CODE ###

n = int(input())
arr = list(map(int,input().split()))
ans = 0
for i in range(len(arr)):
    for j in range(i+1,len(arr)):
        ans += (arr[i]*arr[j])%(1000000007)
        ans %= 1000000007
print(ans)

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
ans = 0
tmp = 0

for i in range(n-1):
    tmp += arr[i]%1000000007
    ans += tmp*arr[i+1] % 1000000007

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

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

from collections import Counter

m = Counter(S)

ans = m['R']*m['G']*m['B']
non = 0


for i in range ((N-1)//2):
    st = 0
    while st + (i+1)*2 < N:
        if S[st] != S[st+i+1] and S[st+i+1] != S[st+2*(i+1)] and S[st] != S[st+2*(i+1)]:
            non += 1
        st += 1
        
print(ans-non)

### FIXED CODE ###

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

from collections import Counter

m = Counter(S)

ans = m['R']*m['G']*m['B']
non = 0


for i in range ((N-1)//2):
    st = 0
    while st + (i+1)*2 < N:
        if S[st] != S[st+i+1] and S[st+i+1] != S[st+2*(i+1)] and S[st] != S[st+2*(i+1)]:
            non += 1
        st += 1
        
print(ans-non)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def c_div(a, b):
    my_list = []
    for i in range(2, min(a, b)+1):
        flag = True
        for item in my_list:
            if i % item == 0:
                flag = False
                break
        if flag and a % i == 0 and b % i == 0:
            my_list.append(i)
    return len(my_list)+1


# スペース区切りの整数の入力
a, b = map(int, input().split())
print(c_div(a, b))


### FIXED CODE ###

# -*- coding: utf-8 -*-
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


# スペース区切りの整数の入力
a, b = map(int, input().split())
a_list = prime_factorize(a)
a_set = set(a_list)
b_list = prime_factorize(b)
b_set = set(b_list)

print(len(a_set & b_set)+1)
### BUGGY CODE ###

N,M = map(int,input().split())
list = []
 
for i in range(M):
  L,R = map(int,input().split())
  list.extend(range(L,R + 1))
 
unq = set(list)

counter = 0
 
for i in unq:
  if list.count(i) == M:
    counter +=1
    
print(counter)

### FIXED CODE ###

N,M = map(int,input().split())
L_list = []
R_list = []

for i in range(M):
  L,R = map(int,input().split())
  L_list.append(L)
  R_list.append(R)
  
if min(R_list) >= max(L_list):
  print(min(R_list)  - max(L_list)+1)
else:
  print(0)
### BUGGY CODE ###

N = int(input())
Counted = []
num = [0 for _ in range(N)]
 
for i in range(N):
  S = input()
  if S in Counted:
    num[Counted.index(S)] += 1
  else:
    Counted.append(S)
    num[Counted.index(S)] += 1

Dict = list(zip(Counted, num))
Dict_sorted = sorted(Dict,key=lambda x: x[1], reverse = True)
 
VVV = []
 
for i in range(len(Dict_sorted)):
  if Dict_sorted[i][1] == Dict_sorted[0][1]:
    VVV.append(Dict_sorted[i][0])
  else:
    break

SSS = sorted(VVV)
 
for _ in range(len(SSS)):
  print(SSS[_])

### FIXED CODE ###

N = int(input())
dic = {}
Max = 1

for _ in range(N):
  S = input()
  if not S in dic:
    dic[S] = 1
  else:
    dic[S] += 1
    Max = max([Max, dic[S]])

ans = []
    
for x in dic:
  if dic[x] == Max:
    ans.append(x)

ans_sorted = sorted(ans)
for y in range(len(ans)):
  print(ans_sorted[y])
### BUGGY CODE ###

n, k, q = map(int, input().split())
S = []
A = []

for i in range(n) :
    S.append(int(k))

for a in range(q) :
    A.append(int(input()))

for i in range(n) :
    S[i] = S[i] - len(A) + A.count(i+1)

for i in range(n) :
    if S[i] > 0 :
        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 ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [[0]*(l-3) for i in range(l-3)]
#print(mod)
mod2 = [[0]*9 for i in range(l-3)]
for i in range(l-3):
    for j in range(1,10):
        mod2[i][j-1] = (j*pow(10,i+3,2019))%2019
#print(mod2)
for w in range(4,l+1):
    for i in range(l+1-w):
        j = i + w
        if (w == 4):
            m = (mod2[0][int(s[i])-1]+int(s[i+1:j]))%2019
            mod[w-4][i] = m
            if m == 0:
                cnt += 1
        else:
            m = (mod2[w-4][int(s[i])-1]+mod[w-5][i+1])%2019
            mod[w-4][w-4+i] = m
            if m == 0:
                cnt += 1
#print(mod)
print(cnt)

### FIXED CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [0]*2019
m = 0
for i in range(l):
    m = (int(s[l-1-i])*pow(10,i,2019) + m)%2019
    mod[m] += 1

cnt += mod[0]

for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))/2
        #print(i)
print(int(cnt))
### BUGGY CODE ###

from itertools import combinations, chain

H, W, K = map(int, input().split())
Sss = []
for _ in range(H):
    Sss.append(list(map(int, input())))


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    return min(map(lambda Sss: _v_end(Sss, start, K), Ssss))


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < start:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)


### FIXED CODE ###

from itertools import combinations, chain

H, W, K = map(int, input().split())
Sss = []
for _ in range(H):
    Sss.append(list(map(int, input())))


def h_divide(Sss, div_is):
    result = []
    for s, e in zip(chain([0], div_is), chain(div_is, [len(Sss)])):
        result.append(Sss[s:e])
    return result


def _v_end(Sss, start, K):
    count = 0
    for i in range(start, len(Sss[0])):
        s = sum(map(lambda Ss: Ss[i], Sss))
        if count + s > K:
            return i - 1
        count += s
    return len(Sss[0]) - 1


def v_end(Ssss, start, K):
    result = -1
    for Sss in Ssss:
        end = _v_end(Sss, start, K)
        if end < start:
            return -1
        if result < 0 or result > end:
            result = end
    return result


def v_div_count(Ssss, K):
    start, result = 0, 0
    while True:
        end = v_end(Ssss, start, K)
        if end < 0:
            return -1
        if end == len(Ssss[0][0]) - 1:
            break
        result += 1
        start = end + 1
    return result


h_cands = list(range(1, len(Sss)))
ans = -1
for n in range(len(h_cands) + 1):
    for comb in combinations(h_cands, n):
        if ans > 0 and n >= ans:
            continue
        Ssss = h_divide(Sss, list(comb))
        cnt = v_div_count(Ssss, K)
        if cnt < 0:
            continue
        if ans < 0 or ans > n + cnt:
            ans = n + cnt
print(ans)