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

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


def LCSubStr(X, Y, m, n):

    # Create a table to store lengths of
    # longest common suffixes of substrings.
    # Note that LCSuff[i][j] contains the
    # length of longest common suffix of
    # X[0...i-1] and Y[0...j-1]. The first
    # row and first column entries have no
    # logical meaning, they are used only
    # for simplicity of the program.

    # LCSuff is the table with zero
    # value initially in each cell
    LCSuff = [[0 for k in range(n+1)] for l in range(m+1)]

    # To store the length of
    # longest common substring
    result = 0

    # Following steps to build
    # LCSuff[m+1][n+1] in bottom up fashion
    for i in range(m + 1):
        for j in range(n + 1):
            if (i == 0 or j == 0):
                LCSuff[i][j] = 0
            elif (X[i-1] == Y[j-1]):
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1
                result = max(result, LCSuff[i][j])
            else:
                LCSuff[i][j] = 0
    return result


ans = 0
for i in range(1, N):
    ls = LCSubStr(S[:i], S[i:], i, N-i)
    ans = max(ans, ls)
    # if len(ls) > ans:
    #     ans = len(ls)


print(ans)


### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for d in range(1, n):
    count = 0
    for i in range(n-d):
        if s[i] == s[i+d]:
            count += 1
        else:
            count = 0
        ans = max(min(count, d), ans)
print(ans)
### BUGGY CODE ###


def main():
    
    N = int(input())

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

    # check = [[True] + [False] * (N - 2) for _ in range(N)] #True準備完了、False試合不可
    check = [0] * N #i番目の次の相手のindex

    ans = 0
    i = 0
    tmp = 0
    count = 0
    while tmp < N + 1000:
        if i % N == 0:
            ans += 1
            flag  = [True] * N #試合をしたかどうかチェック
            i = 0
            
        if check[i] >= N - 1 or flag[i] == False:
            i += 1
            tmp += 1
            continue
        b = A[i][check[i]]
        # print (b)
        if A[b - 1][check[b - 1]] - 1 == i and flag[b - 1]: #試合できる時
            check[i] += 1
            check[b - 1] += 1
            flag[i] = False
            flag[b - 1] = False
            tmp = 0
            count += 1
            if count == (N * (N - 1))//2:
                print (ans)
                exit()
        i += 1
        tmp += 1
    
    print (-1)
    return 
            
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

N = int(input())
A = [list(reversed(list(map(lambda x: int(x) - 1, input().split())))) for _ in range(N)]
B = {i: row for i, row in enumerate(A)}

# print (A)
# print (B)

end = 0

for k in range(8000):
    used = set()
    dels = []
    for i, q in B.items():
        if not q:
            continue
        if i in used:
            continue
        j = q[-1]
        if j in used:
            continue
        if A[j][-1] == i:
            A[j].pop()
            A[i].pop()
            used.add(i)
            used.add(j)
            if not A[i]:
                end += 1
                dels.append(i)
            if not A[j]:
                end += 1
                dels.append(j)
    if not used:
        print (-1)
        exit()
    
    if end == N:
        print (k + 1)
        exit()
    
    for i in dels:
        del B[i]
        
print (N * (N - 1) // 2)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
  query = input()
  if query == "1": S = S[::-1]
  elif query[2] == "1": S = query[4] + S
  else: S = S + query[4]
print(S)  

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
rev = 0
for i in range(Q):
  query = input()
  if query == "1": rev = 1 - rev 
  elif int(query[2]) + rev == 2: S.append(query[4])
  else:S.appendleft(query[4])
if rev == 1: S.reverse()  
print("".join(S))
### BUGGY CODE ###

import sys


n=int(input())
D=list(map(int,input().split()))
M=int(input())
T=list(map(int,input().split()))
D.sort()
T.sort()
Dd={}
Td={}
Ds=set(D)
Ts=set(T)
for i in Ds:
    Dd[i]=D.count(i)
for i in Ts:
    Td[i]=T.count(i)
for i in Td.keys():
    if(i in Dd):
        if(Td[i]>Dd.get(i)):
            print("NO")
            sys.exit()
    else:
        print("NO")
        sys.exit()
print("YES")

### FIXED CODE ###

import sys
from collections import Counter


n=int(input())
Dc=Counter(input().split())
m=int(input())
Tc=Counter(input().split())
for key,val in Tc.items():
    if(val>Dc[key]):
        print("NO")
        sys.exit()
print("YES")
### BUGGY CODE ###

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        k = j+1
        while k < n and l[k] > max(l[i]-l[j], l[j]-l[i]):
            k += 1
            ans += 1
print(ans)


### FIXED CODE ###

import bisect

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

l.sort()
ans = 0
for i in range(n-1):
    b = l[:i]
    c = l[i+1:]
    for j in b:
        ans += bisect.bisect_left(c, l[i] + j)#2番目の棒より短く(left), 一定以上の長さを持つ([i+1:])
print(ans)
### BUGGY CODE ###

from collections import deque
N,M,P,*L = map(int, open(0).read().split())
INF = 10**9
Els = []
dic = [[] for i in range(N+1)]
rdic = [[] for i in range(N+1)]
for a,b,c in zip(*[iter(L)]*3):
  dic[a].append((b,c-P))
  rdic[b].append((a,c-P))
  Els.append((a,b,-c+P))
ok1 = [False]*(N+1)
ok1[1] = True
q = deque([1])
while q:
  v = q.popleft()
  for p,c in dic[v]:
    if not ok1[p]:
      ok1[p] = True
      q.append(p)

ok2 = [False]*(N+1)
ok2[N] = True
q = deque([N])
while q:
  v = q.popleft()
  for p,c in rdic[v]:
    if not ok2[p]:
      ok2[p] = True
      q.append(p)

ok = [a&b for a,b in zip(ok1,ok2)]

dist = [INF]*(N+1)
dist[1] = 0
cnt = 0
while True:
  end = True
  for a,b,c in Els:
    if ok[a] and ok[b] and dist[a]!=INF and dist[b]>dist[a]+c:
      end = False
      dist[b] = dist[a]+c
  if end:
    print(max(0,-dist[N]))
    break
  cnt += 1
  if cnt>2*M:
    print(-1)
    break

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)
N, M, P = map(int,input().split())
es = []
to = defaultdict(list)
rto = defaultdict(list)
rf = [False]*N
rt = [False]*N
for i in range(M):
  a, b, c = map(int, input().split())
  es += [(a-1,b-1,-c+P)]
  to[a-1] += [b-1]
  rto[b-1] += [a-1]

def dfs(v):
  if rf[v]:
    return
  rf[v] = True
  for u in to[v]:
    dfs(u)

def rdfs(v):
  if rt[v]:
    return
  rt[v] = True
  for u in rto[v]:
    rdfs(u)

dfs(0)
rdfs(N-1)
ok = [False]*N
for i in range(N):
  ok[i] = rf[i]&rt[i]

dist = [float('inf')]*N
dist[0] = 0
upd = True
cnt = 0
while upd:
  upd = False
  for j in range(M):
    f, t, c = es[j]
    if (not ok[f]) or (not ok[t]):
      continue
    if dist[t]>dist[f]+c:
      upd = True
      dist[t] = dist[f]+c
  cnt += 1
  if cnt>N:
    print(-1)
    break
else:
  print(max(0,-dist[N-1]))
### BUGGY CODE ###

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

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}
move = [0] * (H*W + 1)

for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    move[i] = abs(a%W - b % W) + abs(a//W - b//W)

for l,r in LR:
    if l == r:
        print(0)
        continue
    print(sum(move[l+D:r+1:D]))
    

### FIXED CODE ###

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

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}

memo = [0] * (H*W+1)
for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    memo[i] = memo[i-D] + abs(a%W - b % W) + abs(a//W - b//W)

for l,r in LR:
    if l == r:
        print(0)
        continue
    print(memo[r] - memo[l])
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  print(Si.count('AC'))

### FIXED CODE ###

N, Q = map(int,input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

n=int(input())
ans=[]
tt=0
for i in range(n):
    s=list(input())
    s.sort()
    s="".join(s)
    ans.append(s)
for i in range(n-1):
    for j in range(i+1,n):
        if ans[i]==ans[j]:
            tt+=1
print(tt)

### FIXED CODE ###

from collections import Counter
n=int(input())
ans=[]
tt=0
for i in range(n):
    s=list(input())
    s.sort()
    s="".join(s)
    ans.append(s)
l=Counter(ans)
c=l.most_common()
for i,j in c:
    tt+=j*(j-1)//2
print(tt)
### BUGGY CODE ###

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数

N,W = imn()
wv = [iln() for _ in range(N)]

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for sum_w in range(0,W+1):
        if (sum_w - wv[i][0]) >= 0: 
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w-wv[i][0]]+wv[i][1]) 

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


### FIXED CODE ###

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

dp = [[0 for _ in range(W+1)] for _ in range(N+1)] 

dp[0][0] = 0

for i in range(N):
    weight = wv[i][0]
    for j in range(W+1):
        dp[i+1][j] = dp[i][j]
        if j >= weight:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight] + wv[i][1])
print(dp[N][W])
### BUGGY CODE ###

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

dp = [-1]*N
dp[0] = 0
dp[1] = abs(h[0] - h[1])

for i in range(2,N):
  index = i - K
  if index < 0: index = 0

  dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(index,i))
print(dp[N-1])

### FIXED CODE ###

def main():
  N,K= map(int,input().split())
  h = list(map(int,input().split()))
  dp = [0]*N
  for i in range(1,N):
    dp[i] = min(dp[j] + abs(h[i] - h[j]) for j in range(max(i-K,0),i))
  print(dp[N-1])

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

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

A.insert(0,0)
A.append(0)
_A = []

for i in range(1,N+1):
  _A.append(abs(A[i] - A[i-1]))
_A.append(abs(0-A[N]))
S = sum(_A)


for i in range(0,N):
  allS = sum(_A)
  allS -= (_A[i]+_A[i+1]-abs(A[i+2]-A[i]))
  print(allS)

### FIXED CODE ###

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

A.insert(0,0)
A.append(0)
_A = []

for i in range(1,N+1):
  _A.append(abs(A[i] - A[i-1]))
_A.append(abs(0-A[N]))
S = sum(_A)


for i in range(0,N):
  allS = S
  allS -= (_A[i]+_A[i+1]-abs(A[i+2]-A[i]))
  print(allS)
### BUGGY CODE ###


def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * max(N,K)
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

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

import itertools
n,y = map(int,input().split())
z = y//1000

list = list(range(n+1))
for a,b,c in itertools.product(list,list,list):
    v = 10*a + 5*b + c
    w = a + b + c
    if v == z and w == n:
        break
else:
    a = -1
    b = -1
    c = -1

print(str(a),str(b),str(c))

### FIXED CODE ###

import itertools
n,y = map(int,input().split())
z = y//1000

list = list(range(n+1))
for a,b in itertools.product(list,list):
    c = n - a - b
    if c>=0:
        v = 10*a + 5*b + c
        w = a + b + c
        if v == z and w == n:
            break
else:
    a = -1
    b = -1
    c = -1

print(str(a),str(b),str(c))
### BUGGY CODE ###

S = input()
Q = int(input())

for i in range(Q):
    Q = [i for i in input().split()]
    if Q[0] == "1":
        S = S[::-1]
    else:
        if Q[1] == "1":
            S = Q[2] + S
        elif Q[1] == "2":
            S = S + Q[2]

print(S)

### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())

sign = 1
head = ""
tail = ""
for i in range(Q):
    Q = input().split()
    if Q[0] == "1":
        sign *= -1
    else:
        if int(Q[1]) * sign == 1:
            S.appendleft(Q[2])
        elif int(Q[1]) * sign == -1:
            S.append(Q[2])
        elif int(Q[1]) * sign == 2:
            S.append(Q[2])
        elif int(Q[1]) * sign == -2:
            S.appendleft(Q[2])

if sign==1:
    print("".join(S))
elif sign==-1:
    S.reverse()
    print("".join(S))
### BUGGY CODE ###

from collections import Counter
def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    n = float(n)
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        if dp[i][j][k]:
            return dp[i][j][k]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dp[i][j][k] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

import collections
import sys
sys.setrecursionlimit(10**7)

def calc(one,two,three):
  zero=n-one-two-three
  if (one,two,three) in memo:
    return memo[(one,two,three)]
  ret=0
  if zero!=n:
    ret=1/(1-zero/n)
  if one!=0:
    ret+=(calc(one-1,two,three)*one/n)/(1-zero/n)
  if two!=0:
    ret+=(calc(one+1,two-1,three)*two/n)/(1-zero/n)
  if three!=0:
    ret+=(calc(one,two+1,three-1)*three/n)/(1-zero/n)
  memo[(one,two,three)]=ret
  return ret

n=int(input())
arr=list(map(int,input().split()))
memo=collections.defaultdict(int)
cnt=[0,0,0,0]
for val in arr:
  cnt[val]+=1
calc(cnt[1],cnt[2],cnt[3])
print(memo[(cnt[1],cnt[2],cnt[3])])

### FIXED CODE ###

import collections

n=int(input())
arr=list(map(int,input().split()))
dp=[[[0]*(n+1) for _ in range(n+1)] for _ in range(n+1)]
cnt=collections.Counter(arr)
for total in range(1,n+1):
  for three in range(total+1):
    for two in range(total-three+1):
      one=total-two-three
      dp[one][two][three]+=n/total
      if one!=0:
        dp[one][two][three]+=dp[one-1][two][three]*one/total
      if two!=0:
        dp[one][two][three]+=dp[one+1][two-1][three]*two/total
      if three!=0:
        dp[one][two][three]+=dp[one][two+1][three-1]*three/total
print(dp[cnt[1]][cnt[2]][cnt[3]])
### BUGGY CODE ###

import math

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

for i in range(M):
    price.sort(reverse=True)
    price[0] = math.floor(price[0] / 2)
print(sum(price))

### FIXED CODE ###

import heapq

N, M = list(map(int, input().split()))
price = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(price)

for i in range(M):
    max_price = -(heapq.heappop(price))
    new_price = max_price // 2
    heapq.heappush(price, -(max_price // 2))

print(-(sum(price)))
### BUGGY CODE ###

N = int(input())

def adjust(a, b, va, vb):
  if a == 0 and b == 0:
    return va, vb
  if vb == 1:
    return a, b
  while a / b != va / vb:
    if a / b < va / vb:
      a += 1
    elif a / b > va / vb:
      b += 1
  return a, b

t = 0
a = 0
for n in range(N):
  ti, ai = [int(x) for x in input().split()]
  if ti < ai:
    t, a = adjust(t, a, ti, ai)
  else:
    a, t = adjust(a, t, ai, ti)

print(t + a)

### FIXED CODE ###

N = int(input())

def adjust(a, b, va, vb):
  r = max(a // va, b // vb)
  if va * r < a or vb * r < b:
    r += 1
  
  return va * r, vb * r

t, a = [int(x) for x in input().split()]
for n in range(N - 1):
  ti, ai = [int(x) for x in input().split()]
  t, a = adjust(t, a, ti, ai)

print(t + a)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
c = int(N/2) - 1
for i in range(N):
    Y = X[:]
    Y .pop(i)
    Y.sort()
    print(Y[c])

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
Y = sorted(X)
n = int(N/2) 
for e in X:
    if e <= Y[n-1]:
        print(Y[n])
    elif e >= Y[n]:
        print(Y[n-1])
### BUGGY CODE ###

import numpy as np

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

a_list= np.array(a)

def light(a_list):
    outcome= np.array([0]*n)
    for i in range(n):
        outcome[max(0,i-a_list[i]):min(n,i+a_list[i]+1)] += 1
    return outcome

for _ in range(k):
    if sum(a) >= n*n:
        break
    a = light(a)

[print(aa,end=' ') for aa in a]

### FIXED CODE ###

import numpy as np
from numba import njit

n,k =map(int,input().split())
a= np.array(list(map(int,input().split())))

@njit(cache=True)
def light(n,a_list):
    outcome= np.zeros(n+1, dtype=np.int64)
    for i in range(n):
        outcome[max(0,i-a_list[i])] += 1
        outcome[min(n,i+a_list[i]+1)] -= 1
    outcome = np.cumsum(outcome)[:-1]
    return outcome

for _ in range(k):
    if min(a) == n:
        break
    a = light(n,a)

[print(aa,end=' ') for aa in a]
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=998244353
cntb=1
ans=0
for i in range(k+1):
    # cntb*=(n-i)//i
    ans+=(((m*pow(m-1,n-1-i,mod))%mod)*cntb)%mod
    ans%=mod
    cntb*=((n-1-i)*pow(i+1,mod-2,mod))%mod
print(ans%mod)

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=998244353
cntb=1
ans=0
for i in range(k+1):
    ans=ans+(((m*pow(m-1,n-1-i,mod))%mod)*cntb)%mod
    ans=ans%mod
    cntb=(cntb*(n-1-i)*pow(i+1,mod-2,mod))%mod
print(ans%mod)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans= 0
tmp=0
for i in range(n-k+1):
    # print(i,tmp,p[i:i+k])
    if sum(p[i:i+k])>tmp:
        # print(i,tmp)
        tmp = sum(p[i:i+k])
        ans= i
anss=0
for j in p[ans:ans+k]:
    anss+=(j+1)/2


print(anss)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans= 0
tmp=0
sump=sum(p[0:k])
for i in range(n-k):
    sump=sump+p[i+k]-p[i]
    # print(i,tmp,p[i:i+k])
    if sump>tmp:
        # print(i,tmp)
        tmp = sump
        ans= i+1
anss=0
for j in p[ans:ans+k]:
    anss+=(j+1)/2


print(anss)
### BUGGY CODE ###

import math

n,a,b=map(int,input().split())
d={}


def cc(n, r):
    if not d.get(n):
        d[n] = math.factorial(n)
    if not d.get(n-r):
        d[n-r] = math.factorial(n-r)
    if not d.get(r):
        d[r] = math.factorial(r)

    return d[n] // (d[n-r] * d[r])


x=10**9 +7
r=0
for i in range(1,n+1):
    if i == a or i == b:continue
    
    r+=cc(n,i)



print(r%x)

### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10 ** 9 + 7
 
 
def cmb(n, r, mod):
    r = min(r, n - r)
    x = 1
    y = 1
    for i in range(r):
        x = x * (n - i) % mod
        y = y * (i + 1) % mod
    y = pow(y, mod-2, mod)
    return x * y % mod
 

ans = pow(2, n, mod) - 1 - cmb(n, a, mod) - cmb(n, b, mod)
while ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    for c in X:
        x <<= 1
        if c == "1":
            x |= 1
    X = x
    # wa+1
    px = X % (wa+1)
    if wa != 1:
        nx = X % (wa-1)
    else:
        nx = None

    for i, c in enumerate(origX):
        count = 0
        x = X ^ (1 << N-i-1)
        if c == "1":
            if x == 0:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            count += 1
            while x != 0:
                count += 1
                x %= bit_sum(x)
            print(count)
        else:
            if x == 0:
                print(0)
                continue
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            count += 1
            while x != 0:
                count += 1
                x %= bit_sum(x)
            print(count)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


import time


INF = float("inf")
MOD = 10**9 + 7


def bit_sum(n):
    wa = 0
    while n > 0:
        wa += n & 1
        n >>= 1
    return wa

def bit(n, k):
    return (n >> k) & 1

def main():
    start = time.time()
    N = INT()
    X = input()
    origX = X
    wa = X.count("1")
    x = 0
    px = 0
    nx = 0
    start = time.time()
    for c in X:
        x <<= 1
        px <<= 1
        nx <<= 1
        if c == "1":
            x |= 1
            px |= 1
            nx |= 1
        px %= (wa+1)
        if wa != 1:
            nx %= (wa-1)
        else:
            nx %= wa
    if wa == 1:
        nx = None
    # print(time.time()-start)
    # start = time.time()
    X = x
    table = [None]*(N+1)
    table[0] = 0
    table[1] = 1
    for i in range(1, N+1):
        table[i] = table[i % bit_sum(i)] + 1
    # print(time.time()-start)
    # start = time.time()

    for i, c in enumerate(origX):
        count = 0
        if c == "1":
            if wa == 1:
                print(0)
                continue
            x = (nx-pow(2, N-i-1, wa-1)) % (wa-1)
            print(table[x]+1)
        else:
            x = (px+pow(2, N-i-1, wa+1)) % (wa+1)
            print(table[x]+1)
    # print(time.time()-start)
    return


if __name__ == '__main__':
    main()