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

def solve(n, s):
    rlist, glist, blist = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
    rcount, gcount, bcount = 0, 0, 0
    for i in range(n-1):
        if s[n-1-i] == 'R':
            rcount += 1
        if s[n-1-i] == 'G':
            gcount += 1
        if s[n-1-i] == 'B':
            bcount += 1
        rlist[n-2-i], glist[n-2-i], blist[n-2-i] = rcount, gcount, bcount
        
    ans = 0

    for i in range(len(s)-2):
        for j in range(i+1,len(s)-1):
            if s[i] != s[j]:
                if s[i] == 'R':
                    if s[j] == 'G':
                        ans += blist[j] - ( 1 if 2*j-i < n and s[2*j-i] == 'B' else 0)
                    elif s[j] == 'B':
                        ans += glist[j] - (1 if 2*j-i < n and s[2*j-i] == 'G' else 0)
                elif s[i] == 'G':
                    if s[j] == 'R':
                        ans += blist[j] - (1 if 2*j-i < n and s[2*j-i] == 'B' else 0)
                    elif s[j] == 'B':
                        ans += rlist[j] - (1 if 2*j-i < n and s[2*j-i] == 'R' else 0)
                elif s[i] == 'B':
                    if s[j] == 'G':
                        ans += rlist[j] - (1 if 2*j-i < n and s[2*j-i] == 'R' else 0)
                    elif s[j] == 'R':
                        ans += glist[j] - (1 if 2*j-i < n and s[2*j-i] == 'G' else 0)
    
    return ans

def main():
    n = int(input())
    s = input()
    print(solve(n, s))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def solve(n, s):
    rlist, glist, blist = [0 for _ in range(n)], [0 for _ in range(n)], [0 for _ in range(n)]
    rcount, gcount, bcount = 0, 0, 0
    for i in range(n-1):
        if s[n-1-i] == 'R':
            rcount += 1
        if s[n-1-i] == 'G':
            gcount += 1
        if s[n-1-i] == 'B':
            bcount += 1
        rlist[n-2-i], glist[n-2-i], blist[n-2-i] = rcount, gcount, bcount
        
    ans = 0

    for i in range(n-2):
        for j in range(i+1,n-1):
            if s[i] != s[j]:
                if s[i] == 'R':
                    if s[j] == 'G':
                        ans += blist[j] - ( 1 if 2*j-i < n and s[2*j-i] == 'B' else 0)
                    else:
                        ans += glist[j] - (1 if 2*j-i < n and s[2*j-i] == 'G' else 0)
                elif s[i] == 'G':
                    if s[j] == 'R':
                        ans += blist[j] - (1 if 2*j-i < n and s[2*j-i] == 'B' else 0)
                    else:
                        ans += rlist[j] - (1 if 2*j-i < n and s[2*j-i] == 'R' else 0)
                else:
                    if s[j] == 'G':
                        ans += rlist[j] - (1 if 2*j-i < n and s[2*j-i] == 'R' else 0)
                    else:
                        ans += glist[j] - (1 if 2*j-i < n and s[2*j-i] == 'G' else 0)
    
    return ans

def main():
    n = int(input())
    s = input()
    print(solve(n, s))

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

import functools

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

def gcd(nums):
    return functools.reduce(euclid, nums)

N = int(input())
A = list(map(int,(input().split())))
L = [0]*N
R = [0]*N

for i in range(N):
    L[i] = gcd(A[0:i+1])
for i in range(N):
    R[i] = gcd(A[N-1-i:N])

p = []

for i in range(N):
    if i == 0:
        p.append(gcd(R[0:N-1]))
    elif i == N-1:
        p.append(gcd(L[0:N-1]))
    else:
        p.append(gcd ( [gcd(L[0:i]),gcd(R[0:N-1-i])]) )

print(max(p))

### FIXED CODE ###

import functools

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

def gcd(nums):
    return functools.reduce(euclid, nums)

N = int(input())
A = list(map(int,(input().split())))
L = [0]*N
R = [0]*N
L[0] = A[0]
R[0] = A[N-1]
for i in range(1,N):
    L[i] = gcd([L[i-1],A[i]])
for i in range(1,N):
    R[i] = gcd([R[i-1],A[N-1-i]])

p = []

for i in range(N):
    if i == 0:
        p.append(R[N-2])
    elif i == N-1:
        p.append(L[N-2])
    else:
        p.append( gcd([L[i-1], R[N-2-i]]) )

print(max(p))
### BUGGY CODE ###

import itertools
n = int(input())
s = input()

print(len(set(list(itertools.combinations(s, 3)))))


### FIXED CODE ###

# TLE

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

count = 0
for a in range(10):
    for b in range(10):
        for c in range(10):
            f1 = False
            f2 = False
            p1 = 0
            p2 = 0
            for i in range(0, n-2):
                if int(s[i]) == a:
                    f1 = True
                    p1 = i
                    break
            if f1:
                for j in range(p1+1, n-1):
                    if int(s[j]) == b:
                        f2 = True
                        p2 = j
                        break
            if f2:
                for k in range(p2+1, n):
                    if int(s[k]) == c:
                        count += 1
                        break
            if not f1 or not f2:
                break
print(count)
### BUGGY CODE ###

class Solution:

    def solve(self, N: int, M: int) -> int:

        mod = 10**9+7
        INT_MAX = 10**6

        # calculate {m+n}C{n}

        def egcd(a, b):
            if a == 0:
                return b, 0, 1
            else:
                g, y, x = egcd(b % a, a)
                return g, x - (b // a) * y, y

        def modinv(a, m):
            g, x, y = egcd(a, m)
            if g != 1:
                raise Exception('modular inverse does not exist')
            else:
                return x % m

        def combination(n: int, r: int, mod: int = 10**9+7) -> int:
            r = min(r, n-r)
            res = 1
            for i in range(r):
                res = res * (n-i) * modinv(i+1, mod) % mod
            return res

        # prime list

        isPrime = [True] * (INT_MAX + 1)
        isPrime[0], isPrime[1] = False, False
        primes = []

        for i in range(2, len(isPrime)):
            if isPrime[i] == True:
                primes.append(i)
                for j in range(2 * i, len(isPrime), i):
                    isPrime[j] = False

        # solve

        m = M
        answer = 1
        factors = {}
        while m > 1:
            for p in primes:
                factors[p] = 0

                while m % p == 0:
                    m //= p
                    factors[p] += 1

                if factors[p] > 0:
                    answer *= combination(N + factors[p] - 1, N - 1, mod=mod)
                    answer %= mod

        return answer


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())

    # solve
    solution = Solution()
    print(solution.solve(N, M))


### FIXED CODE ###

import math


class Solution:

    def solve(self, N: int, M: int) -> int:

        mod = 10**9+7
        INT_MAX = 10**9

        # calculate {m+n}C{n}

        def egcd(a, b):
            if a == 0:
                return b, 0, 1
            else:
                g, y, x = egcd(b % a, a)
                return g, x - (b // a) * y, y

        def modinv(a, m):
            g, x, y = egcd(a, m)
            if g != 1:
                raise Exception('modular inverse does not exist')
            else:
                return x % m

        def combination(n: int, r: int, mod: int = 10**9+7) -> int:
            r = min(r, n-r)
            res = 1
            for i in range(r):
                res = res * (n-i) * modinv(i+1, mod) % mod
            return res

        # solve

        m = M
        answer = 1
        factors = {}
        for i in range(2, int(math.sqrt(M))+1):
            factor = 0
            while m % i == 0:
                m //= i
                factor += 1

            if factor > 0:
                answer *= combination(N + factor - 1, N - 1, mod=mod)
                answer %= mod

        if m > 1:
            answer *= N
            answer %= mod

        return answer


if __name__ == '__main__':

    # standard input
    N, M = map(int, input().split())

    # solve
    solution = Solution()
    print(solution.solve(N, M))
### BUGGY CODE ###

n=int(raw_input())
a=[0]*n
for i in range(n):
    a[i]=str(raw_input())
s=set(a)
ans=[-1]
m=0
for i in s:
    if(a.count(i)==m):
        m=a.count(i)
        ans.append(i)
    elif(a.count(i)>m):
        m=a.count(i)
        ans.pop()
        ans.append(i)
ans.sort()
for i in ans:
    print i

### FIXED CODE ###

n=int(raw_input())
d={}
for i in range(n):
    x=str(raw_input())
    try:
        d[x]+=1
    except:
        d[x]=0

key_max = max(d.keys(), key=(lambda k: d[k]))
x=d[key_max]
ans=[]
for i in d:
    if(d[i]==x):
        ans.append(i)
ans.sort()
for i in ans:
    print i
### BUGGY CODE ###

n, b, r = map(int, input().split())
count = 0
i = 0
while (n>i):
    count += b
    i += b
    if n<=i:
        print(count - (i-n))
        break
    i += r
    if n<=i:
        print(count)

### FIXED CODE ###

n, b, r = map(int, input().split())
i = 0
hoge = n // (b+r)
count = hoge*b
n = n - hoge*(b+r)
if n == 0:
    print(count)
while (n>i):
    count += b
    i += b
    if n<=i:
        print(count - (i-n))
        break
    i += r
    if n<=i:
        print(count)
### BUGGY CODE ###

from bisect import bisect_left as bil
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def count_kth_bit(k):
    ret = 0
    t = 2**k
    bs = list(sorted([b%(2*t) for b in B]))
    for a in A:
        a %= (2*t)
        i1 = bil(bs, t-a)
        i2 = bil(bs, 2*t-a)
        i3 = bil(bs, 3*t-a)
        ret += (i2-i1) + (N-i3)
    return ret

ans = 0
for k in range(29):
    c = count_kth_bit(k)
    ans += ((c%2) << k)
print(ans)

### FIXED CODE ###

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

def count_kth_bit(k):
    ret = 0
    t = 2**k
    am = list(sorted([a%(2*t) for a in A]))
    bm = list(sorted([b%(2*t) for b in B]))

    r1 = r2 = r3 = 0
    for a in reversed(am):
        while r1 < N and a + bm[r1] < t:
            r1 += 1
        while r2 < N and a + bm[r2] < 2*t:
            r2 += 1
        while r3 < N and a + bm[r3] < 3*t:
            r3 += 1
        ret += (r2-r1) + (N-r3)
    return ret

ans = 0
for k in range(29):
    c = count_kth_bit(k)
    ans += ((c%2) << k)
print(ans)
### BUGGY CODE ###

import math 
[K, S] = list(map(int, input().split()))
count = 0
for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      total = X + Y + Z 
      if total == S:
        count += 1
      if total > S:
        break
      if total < S/2:
        Z += math.floor(S/2)
            
print(count)

### FIXED CODE ###

[K, S] = list(map(int, input().split()))
count = 0
for X in range(K+1):
  for Y in range(K+1):
    Z = S - X - Y
    if 0 <= Z and Z <= K:
      count +=1

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

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)

for a in A:
    if a==max(A):
        print(B[-2])
    else:
        print(B[-1])

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A)
M0 = B[-1]
M1 = B[-2]

for a in A:
    if a==M0:
        print(M1)
    else:
        print(M0)
### BUGGY CODE ###

N,M = map(int, input().split())

if M%N == 0:
    ans = M//N
else:
    for i in range(M//N, 0, -1):
        ama = M - i*N
        if ama%i==0:
            ans = i
            break

print(ans)

### FIXED CODE ###

N,M = map(int, input().split())

if M%N == 0:
    ans = M//N
else:
    for i in range(M//N, 0, -1):
        ama = M - i*N
        if ama%i==0:
            ans = i
            break

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

import itertools

n  = int(input())

max_m = len(str(n))

ans = 0

for m in range(1,max_m+1):
  for i in range(1, m):
    for j in range(1, m-i):
      k = m-i-j
      ls = ['7']*i+['5']*j+['3']*k
      ss = set()
      for l in itertools.permutations(ls):
        s = ''.join(l)
        s = int(s)
        if s in ss:
          continue
        elif s <= n:
          ans += 1
          # print(s)
          ss.add(s)
        else:
          ss.add(s)
print(ans)

### FIXED CODE ###

n = int(input())

def dfs(s):
  ret = 0
  if int(s) > n:
    return 0
  if all(s.count(c) > 0 for c in '753'):
    ret = 1
  for c in '753':
    ret += dfs(s+c)
  return ret

print(dfs('0'))
### BUGGY CODE ###

import math
A,B =map(int,input().split())

def cf(A,B):
    cf=[]
    for i in range(2,min(A,B)+1):
        if A % i == 0 and B % i == 0:
            cf.append(i)
    return cf


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

print(sum([is_prime(one) for one in cf(A,B)])+1)

### FIXED CODE ###

import math
A,B =map(int,input().split())



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

    divisors.sort()
    return divisors

tmp_A = set(make_divisors(A))
tmp_B = set(make_divisors(B))

tmp_set = tmp_A & tmp_B


def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

print(sum([is_prime(one) for one in tmp_set])+1)
### BUGGY CODE ###

n,W = map(int,input().split())
w,v = [0] * n ,[0] * n
for i in range(n):
    w[i] ,v[i] = map(int,input().split())
dp=[[-1 for i in range(W + 1)] for j in range(n + 1)]


def rec(i,j):
    if dp[i][j] !=-1:
        return dp[i][j]
    if i == n:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1 ,j),rec(i + 1,j -w[i]) + v[i])
    dp[i][j] =res
    return res

print(rec(0,W))


### FIXED CODE ###

n,W = map(int,input().split())
w,v = [0] * n ,[0] * n
for i in range(n):
    w[i] ,v[i] = map(int,input().split())

import numpy as np
ndp = np.zeros(W+1,dtype= np.int64)
for w,v in zip(w,v):
    np.maximum(ndp[:-w] + v, ndp[w:], out = ndp[w:])
print(ndp[-1])
### BUGGY CODE ###

N,K=map(int,input().split())
# S=list(map(int,input().split()))
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

ans=0

for i in range(len(S)):
    try:
        t=S[i]-S[i+K]
    except IndexError:
        t=0
    if t<0:
        pass
    else:
        temp=sum(S[i:i+K])
        if ans<temp:
            ans=temp
        else:
            pass
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)
### BUGGY CODE ###

import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = getS()
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


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



### FIXED CODE ###

import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


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

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

N,M = map(int,input().split(" "))
S = input()
T = input()
Answer = int(len(S)*len(T)/gcd(len(S),len(T)))
X = [0 for i in range(Answer)]

for i in range(len(S)):
    X[int(i*Answer/len(S))] = S[i]

for i in range(len(T)):
    if (X[int(i*Answer/len(T))] == 0)or(X[int(i*Answer/len(T))] == T[i]):
        continue
    else:
        print(-1)
        exit()
print(Answer)


### FIXED CODE ###

def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

N,M = map(int,input().split(" "))
S = input()
T = input()
N = len(S)
M = len(T)
x = gcd(N,M)
y = int(N*M/x)

for i in range(x):
    if S[int(i*y/M)] == T[int(i*y/N)]:
        continue
    else:
        print(-1)
        exit()
print(y)
### BUGGY CODE ###

n = int(input())
r = 0
for i in range(n):
    r += i
print(r)


### FIXED CODE ###

n = int(input())
print(n * (n - 1) // 2)
### BUGGY CODE ###

n,k=map(int,input().split())
p=[sum(range(1,i+1))/i for i in list(map(int,input().split()))]
ans=0
for i in range(n):
    if i+k>n:break
    ans=max(ans, sum(p[i:i+k]))
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
p=[(i+1)/2 for i in map(float,input().split())]
MAX=sum(p[0:k])
s=[MAX]*n
for i in range(0,n-k):
    s[i+1]=p[i+k]+s[i]-p[i]
    MAX=max(MAX,s[i+1])
print(MAX)
### BUGGY CODE ###

n = input() # N times
n = int(n)

power = 1

for i in range(1,n+1):
    power = (power * i)

a = power % (10**9 + 7)
print(a)

### FIXED CODE ###

n = int(input())

power = 1

for i in range(1,n+1):
    power = (power * i) % (10**9 + 7)

print(power)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(1000):
    i = str(i).zfill(3)
    tmp = 0
    for j in s:
        if j == i[tmp]:
            tmp += 1
            if tmp == 3:
                cnt += 1
                break
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(1000):
    i = str(i).zfill(3)
    j = s.find(i[0])
    if j != -1:
        k = s[j + 1:].find(i[1])
        if k != -1:
            if s[j + k + 2:].find(i[2]) != -1:
                cnt += 1
print(cnt)
### BUGGY CODE ###

s=input()
k=int(input())
#s=list(input())

t=[]
for i in range(len(s)):
    for j in range(i,len(s)):
        t.append(s[i:j+1])
        
t.sort()
t1=t[0]
t2=[t[0]]
kk=0
for i in range(1,len(t)):
    if t1!=t[i]:
        t2.append(t[i])
        t1=t[i]
        kk=kk+1
        if kk==k-1:
            break
        
print(t2[k-1])        

### FIXED CODE ###

s=input()
k=int(input())
#s=list(input())

#t=[]
#for kk in range(k):
#    t.append(s)

t=["zzzzz"]*k

for i in range(len(s)):
    for j in range(i,min(len(s),i+k)):
        sij=s[i:j+1]
        for kk in range(k):
            if t[kk]==sij:
                break
        if t[kk]>sij:
            t[kk]=sij
            t.sort()
        
print(t[k-1])  
#print(t)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]

from scipy.sparse.csgraph import floyd_warshall
wf=floyd_warshall(a)
if not (a==wf).all() :
    print(-1)
    exit()

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
wf=[list(map(int,input().split())) for i in range(n)]

ans=0
for i in range(n):
    for j in range(i+1,n):
        use=True
        for h in range(n):
            if h!=i and h!=j and wf[i][j] > wf[i][h]+wf[h][j]:
                print(-1)
                exit()
            if h!=i and h!=j and wf[i][j] == wf[i][h]+wf[h][j]:
                use=False
        if use:
            ans+=wf[i][j]
print(int(ans))
### BUGGY CODE ###

import sys


def main():
    input = sys.stdin.readline

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

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1 == 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        cand0 = cand
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

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

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


if __name__ == '__main__':
    main()