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


def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        array = [[0 for i in range(len(b))] for j in range(len(a))]
        """
        for i in range(len(a)):
            if a[i]==b[0]:
                array[i][0]=1
        for j in range(len(b)):
            if b[j]==a[0]:
                array[0][j]=1 
        """
        for i in range(len(a)):
            for j in range(len(b)):
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    c = 0
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = max(
                                        array[i-1][j],
                                        array[i][j-1],
                                        array[i-1][j-1]+c)
        print(array[len(a)-1][len(b)-1])
        #p.pprint(array)
if __name__ == "__main__":
    main()



### FIXED CODE ###

#dj 16D8101012J ito jun
import sys
def search(a,b):
    na=len(a)
    nb=len(b)
    array = [[0]*(nb+1) for _ in range(na+1)]
    for i,x in enumerate(a,1):
        prerow=array[i-1]
        row=array[i]
        for j,y in enumerate(b,1):
            if x == y:
                row[j]=prerow[j-1]+1
            elif prerow[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = prerow[j]
    return array[-1][-1]

n = int(input())
strs = [list(i) for i in sys.stdin.read().splitlines()]
result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
print(*result, sep="\n")
### BUGGY CODE ###

import bisect

n,q = map(int, input().split())
s = input()
lr = []
for i in range(q):
    tmp = list(int(i) for i in input().split())
    tmp[0] -= 1
    tmp[1] -= 1
    lr.append((tmp))
t = list(s)
acs = []
while not s.find('AC') == -1:
    id = s.find('AC')
    acs.append(id + len(acs) * 2)
    t.pop(id)
    t.pop(id)
    s = ''.join(t)

for i in range(q):
    l = lr[i][0]
    r = lr[i][1]
    li = bisect.bisect_left(acs,l)
    ri = bisect.bisect_right(acs,r)
    if ri > 0:
        if acs[ri-1] == r:
            ri -= 1
    print(ri-li)    


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L,R = [], []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

AC = [0] * N

for i in range(1,N):
    if S[i - 1] == 'A' and S[i] == 'C':
        AC[i] = AC[i - 1] + 1
    else:
        AC[i] = AC[i - 1]

for l, r in zip(L, R):
    print(AC[r-1]-AC[l-1])
### BUGGY CODE ###

def eratosthenes(n):
    prime = [2]
    limit = int(n**0.5)
    prime_list = [i + 1 for i in range(2, n, 2)]
    while True:
        p = prime_list[0]
        if limit <= p:
            return prime + prime_list
        prime.append(p)
        prime_list = [e for e in prime_list if e % p != 0]

def prime_factorize(n):
    prime_list = eratosthenes(n)
    arr = []

    for p in prime_list:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            arr.append([p, cnt])

    return arr



n, p = map(int, input().split())

ans = 1

if p == 1:
    print(1)
    exit()

pr_list = prime_factorize(p)

for a, b in pr_list:
    if b >= n:
        ans *= a ** (b // n)

print(ans)


### FIXED CODE ###

def prime_factorize(n):
    arr = []
    if n % 2 == 0:
        cnt = 0
        while n % 2 == 0:
            cnt += 1
            n //= 2
        arr.append([2, cnt])

    p = 3
    while p * p <= n:
        if n % p == 0:
            cnt = 0
            while n % p == 0:
                n //= p
                cnt += 1
            arr.append([p, cnt])
            p += 2
        else:
            p += 2
            continue

    if n != 1:
        arr.append([n, 1])

    return arr



n, p = map(int, input().split())

ans = 1

if p == 1:
    print(1)
    exit()

pr_list = prime_factorize(p)

for a, b in pr_list:
    if b >= n:
        ans *= a ** (b // n)

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

n, m = map(int, input().split())
hils = list(map(int, input().split()))
nuls = list(range(n))
outls = []

for i in range(m):
    a, b = map(int, input().split())
    if hils[a - 1] < hils[b - 1]:
        if a not in outls:
            outls.append(a)
    elif hils[a - 1] == hils[b - 1]:
        if a not in outls:
            outls.append(a)
        if b not in outls:
            outls.append(b)
    else:
        if b not in outls:
            outls.append(b)

a = n - len(outls)
print(a)

### FIXED CODE ###

n, m = map(int, input().split())
hils = list(map(int, input().split()))
nuls = list(range(n))
outls = []

for i in range(m):
    a, b = map(int, input().split())
    if hils[a - 1] < hils[b - 1]:
        if a not in outls:
            outls.append(a)
    elif hils[a - 1] == hils[b - 1]:
        if a not in outls:
            outls.append(a)
        if b not in outls:
            outls.append(b)
    else:
        if b not in outls:
            outls.append(b)

a = n - len(outls)
print(a)
### BUGGY CODE ###

count={}
for i in range(97,97+26):
    count[chr(i)] = 0

text=[]
text_out=""
while True:
    try:
        text.append(input())
    except EOFError:
        text_out="".join(text)

text_lower=text_out.lower()

for letter in text_lower:
    if letter in count:
        count[letter] += 1

for x,y in sorted(count.items()):
    print("{0} : {1}".format(x,y))

### FIXED CODE ###

count={}
for i in range(97,97+26):
    count[chr(i)] = 0

text=[]
while True:
    try:
        text.append(input())
    except EOFError:
        break

text_out="".join(text)
text_lower=text_out.lower()

for letter in text_lower:
    if letter in count:
        count[letter] += 1

for x,y in sorted(count.items()):
    print("{0} : {1}".format(x,y))
### BUGGY CODE ###

n, m = map(int, input().split())

g = m // n
while 1:
    if m % g == 0:
        break
    g -= 1

print(g)

### FIXED CODE ###

n, m = map(int, input().split())

g = m // n
while 1:
    if m % g == 0:
        break
    g -= 1

print(g)
### BUGGY CODE ###

#LとRが変わる点に着目
#その点でどちらに行くかを繰り返す
#lの連続しているところの一番左に行く、rの連続しているところの右に行く
#偶数と奇数の時で変わりそう
#二つ入れた時にその繰り返しになったら止めれば良さそう
#二回を繰り返しの単位としてその二回でできたものが同じになっていれば終了
import copy
s=input()
n=len(s)

a=[1]*n

def make_new_list():
    global s,n,a
    ax=[0]*n
    for i in range(n):
        if s[i]=="L":
            ax[i-1]+=a[i]
        else:
            ax[i+1]+=a[i]
    a=copy.deepcopy(ax)
    return ax



a1=make_new_list()
#print(a1)
a2=make_new_list()
#print(a2)
a3=make_new_list()
#print(a3)
a4=make_new_list()
#print(a4)
while a1!=a3 or a2!=a4:
    #print(a1)
    #print(a2)
    #print(a3)
    #print(a4)
    a1=copy.deepcopy(a3)
    a2=copy.deepcopy(a4)
    a3=make_new_list()
    a4=make_new_list()
print(" ".join(list(map(str,a4))))


### FIXED CODE ###

#こういう問題で実際に動かすやつはあほ、普通にチェンジするとこまで行って、どっちか(偶数だけ離れてるとこ)に集まるやろ
s=input()
n=len(s)
#変わる点というより変わる点にくる集まりを考えるべき
d=0
a=[]
ax=[0]

for i in range(n):
    l=len(ax)
    if l==1:
        if s[i]=="L":
            ax.append(i-1)
            ax.append(i)
        if i==n-1:
            ax.append(i)
            a.append(ax)
    elif l==3:
        if s[i]=="R":
            ax.append(i-1)
            a.append(ax)
            ax=[i]
        elif i==n-1:
            ax.append(i)
            a.append(ax)
m=len(a)
c=[0]*n
for i in range(m):
    #print(type(a[i][1]))
    #print(type(c[a[i][1]]))
    c[a[i][1]]=(a[i][1]-a[i][0])//2+(a[i][3]-a[i][1])//2+1
    c[a[i][2]]=(a[i][2]-a[i][0])//2+(a[i][3]-a[i][2])//2+1

print(" ".join(list(map(str,c))))
### BUGGY CODE ###

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

b=[0]*(n-k+1)
for i in range(n-k+1):
    b[i] += a[i]
    for j in range(k - 1):
        b[i] *= a[i + j + 1]


for l in range(len(b)-1):
    if b[l] < b[l + 1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(n - k):
    if a[i] >= a[i + k]:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

S = input()
S = S[::-1]
N = len(S)
mod = 10 ** 9 + 7

dp = [[0] * 13 for _ in range(N + 10)]
dp[0][0] = 1

for i, s in enumerate(S):
    if s == "?":
        val = tuple(range(10))
    else:
        val = (int(s),)

    digit = pow(10, i, 13)
    for j in range(13):
        for k in val:
            ni = i + 1
            nj = (j + digit * k) % 13
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod

ans = dp[N][5] % mod
print(ans)


### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7

dp = [0]*13
dp[0] = 1

mul = 1
for i, s in enumerate(S[::-1]):
    new = [0]*13
    if s == "?":
        for x in range(13):
            for y in range(10):
                next_x = y * mul + x
                new[next_x % 13] += dp[x]
                new[next_x % 13] %= mod
    else:
        for x in range(13):
            next_x = int(s) * mul + x
            new[next_x % 13] = dp[x]

    dp = new
    mul *= 10
    mul %= 13

ans = dp[5] % mod
print(ans)
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
n = [a,b,c]
for i in range(k):
    t = n[:]
    for i,ind in zip(n,range(3)):
        t[ind] = sum(n)-i
    n=t[:]
print(n[0]-n[1])

### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = 0
if k==0 or k%2==0:
    ans = a-b
else:
    ans = b-a
if len(str(abs(ans)))==20:
    print("Unfair")
else:
    print(ans)
### BUGGY CODE ###

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

a = list(map(lambda x: x - ma + 1, a))

befscore = 1
score = 1
f = True
for i in range(n):
    score = score * a[i]

    if i >= k:
        score = int(score / a[i - k])
        if befscore >= score:
            print("No")
        else:
            print("Yes")

    befscore = score


### FIXED CODE ###

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

a = list(map(lambda x: x - ma, a))

befscore = 1
score = 1
f = True
for i in range(n):
    score = score + a[i]

    if i >= k:
        score = int(score - a[i - k])
        if befscore >= score:
            print("No")
        else:
            print("Yes")

    befscore = score
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    mod=10**9+7
    C=[int(input())for _ in range(n)]
    places=[[] for _ in range(2*10**5+1)]
    for i in range(n):
        places[C[i]].append(i)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        dp[i]=(dp[i]+dp[i-1])%mod
        color=C[i-1]
        it=places[color].index(i-1)
        if it>0:
            j=places[color][it-1]
            if i-1-j>1:
                dp[i]=(dp[i]+dp[j+1])%mod
    print(dp[-1])


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    mod=10**9+7
    stone=[0]*(2*10**5+1)
    stone_last_pos=[-1]*(2*10**5+1)
    dp=[0]*(n+1)
    dp[0]=1
    for i in range(1,n+1):
        c=int(input())
        place=stone_last_pos[c]
        if place==i-1 or place==-1:
            dp[i]=dp[i-1]
        else:
            dp[i]=(dp[i-1]+dp[place])%mod
        stone_last_pos[c]=i
    print(dp[n])


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

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
# 
#     if temp!=1:
#         arr.append([temp, 1])
# 
#     if arr==[]:
#         arr.append([n, 1])
# 
#     return arr

def main():
    k = int(input())
    if k % 2 == 0 or k % 5 == 0:
        print(-1)
        return
    # if is_prime(k):
    #     print(k-1)
    sevens = 0
    for i in range(k):
        sevens = sevens*10+7
        if sevens%k == 0:
            print(i+1)
            return
    print(k-1)

def main2():
    print(777777777%9)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

k=int(input())
rm=7%k
an=-1
for i in range(10**6):
	if rm==0:
		an=i+1;break
	rm=(rm*10+7)%k
print(an)
### BUGGY CODE ###

def attack(H):
    if(H == 1):
        return 1
    else:
        return 1 + attack(H//2) + attack(H//2)

H = int(input())
print(attack(H))


### FIXED CODE ###

H = int(input())
i,result = 0, 0
while(H>0):
    result += 2**i
    i += 1
    H = H // 2
print(result)
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
import numpy as np
def resolve():
    N = ir()
    A = np.array(lr(), np.int32)
    iA = np.argsort(A)
    B = A[iA]
    B = np.append(B, 2*10**5+1)
    c = []
    d = []
    e = []
    tmp = 1
    st = 0
    for i in range(N+1):
        if tmp == B[i]:
            st += 1
        else:
            if st > 1:
                c.append(tmp)
                d.append(st)
                e.append(st*(st-1)//2)
            else:
                c.append(tmp)
                d.append(st)
                e.append(0)
            tmp = B[i]
            st = 1
    ans = []
    tmp = 0
    # print(c, d, e)
    for i in range(N):
        if B[i] > c[tmp]:
            tmp += 1
        num = d[tmp]
        plu = 0
        if num > 2:
            plu = (num-1)*(num-2)//2
        ans.append(sum(e)-e[tmp]+plu)
    # print(ans)
    # print(iA)
    iiA = np.argsort(iA)
    for i in range(N):
        print(ans[iiA[i]])
            
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
# import numpy as np
def resolve():
    N = ir()
    # A = np.array(lr(), np.int32)
    A = lr()
    A = [[A[i], i] for i in range(N)]
    A.append([2*10**5+1, N+1])
    A = sorted(A, key=lambda x: x[0])
    c = []
    d = []
    e = []
    tmp = 1
    st = 0
    for i in range(N+1):
        if tmp == A[i][0]:
            st += 1
        else:
            if st > 1:
                c.append(tmp)
                d.append(st)
                e.append(st*(st-1)//2)
            else:
                c.append(tmp)
                d.append(st)
                e.append(0)
            tmp = A[i][0]
            st = 1
    ans = []
    tmp = 0
    # print(c, d, e)
    se = sum(e)
    for i in range(N):
        if A[i][0] > c[tmp]:
            tmp += 1
        num = d[tmp]
        plu = 0
        if num > 2:
            plu = (num-1)*(num-2)//2
        ans.append([se-e[tmp]+plu, A[i][1]])
    # print(ans)
    # print(iA)
    ans = sorted(ans, key=lambda x: x[1])
    for i in range(N):
        print(ans[i][0])

resolve()
### BUGGY CODE ###

#AGC005A

x=raw_input()
while x.count('ST')>0:
 x=x.replace('ST','')
print len(x)


### FIXED CODE ###

#AGC005A

s=raw_input()
res=0
for c in s:
 if c=='S':
  res+=1
 elif c=='T' and res>0:
  res-=1
print res*2
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = (k // i) ** n % MOD

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD

    print(int(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    """"ここに今までのコード"""
    n, k = map(int, input().split())
    MOD = 10 ** 9 + 7
    ans = 0
    baig = [0 for i in range(10 ** 5 + 1)]

    for i in range(1, k + 1):
        baig[i] = pow(k // i , n , MOD)

    for j in range(k, 0, -1):
        for jj in range(2 * j, k + 1, j):
            baig[j] -= baig[jj]
        baig[j] %= MOD
        ans += baig[j] * j
        ans %= MOD
    print(int(ans))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a = int(input())
inputList = input().split()


index = 0
sum = 0
for i in range(a - 1):
  for j in range(i + 1, a):
    sum += (int(inputList[i]) ^ int(inputList[j]))

print(sum % (10 **9 + 7))


### FIXED CODE ###

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

mod = 10**9 + 7
total = 0
for i in range(60):
  cnt = sum([1 for a in A if (a>>i & 1)])
  total += cnt * (n-cnt) * (1 << i)
  total %= mod
print(total)
### BUGGY CODE ###

import math
import itertools
from collections import deque
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def lIN(): return list(input())
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
ans = 0

def bfs(sx,sy,gx,gy):
    d = [[float("inf")] * w for i in range(h)]

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

    que = deque([])
    que.append((sx, sy))#スタート座標の記録
    d[sx][sy] = 0#スタートからスタートへの最短距離は0

    while que:#中身がなくなるまで
        p = que.popleft()
        if p[0] == gx and p[1] == gy:#ゴールなら終わり
            break
        for m in range(4):#現在地から4方向の移動を考える
            nx = p[0] + dx[m]
            ny = p[1] + dy[m]

            if 0 <= nx < h and 0 <= ny < w:
              if maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))#↑格子点からでない＆壁でない＆まだ通ってない
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


h, w = map(int, input().split())
maze = [lIN() for i in range(h)]

for i in range(h):#sx座標指定0~h-1
  for j in range(w):#sy座標指定0~w-1
    if maze[i][j] == '#':
      continue
    else:
      for k in range(h):#gx座標指定
        for l in range(w):#gy座標指定
          if maze[k][l] == '.':
            ans = max(bfs(i,j,k,l),ans)
    
print(ans)

### FIXED CODE ###

import math
import itertools
from collections import deque
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def lIN(): return list(input())
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
ans = 0

def bfs(sx,sy):
    d = [[-1] * w for i in range(h)]
    MAX = 0

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

    que = deque([])
    que.append((sx, sy))#スタート座標の記録
    d[sx][sy] = 0#スタートからスタートへの最短距離は0

    while que:#中身がなくなるまで
        p = que.popleft()
       
        for m in range(4):#現在地から4方向の移動を考える
            nx = p[0] + dx[m]
            ny = p[1] + dy[m]

            if 0 <= nx < h and 0 <= ny < w:
              if maze[nx][ny] != "#" and d[nx][ny] == -1:
                que.append((nx, ny))#↑格子点からでない＆壁でない＆まだ通ってない
                d[nx][ny] = d[p[0]][p[1]] + 1

    for k in range(h):
      MAX = max(max(d[k]),MAX)
      
    return MAX

h, w = map(int, input().split())
maze = [lIN() for i in range(h)]

for i in range(h):#sx座標指定0~h-1
  for j in range(w):#sy座標指定0~w-1
    if maze[i][j] == '.':
      ans = max(bfs(i,j),ans)
      
print(ans)
### BUGGY CODE ###

n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

for i in range(q):
    l, r=map(int, input().split())
    l_list.append(l)
    r_list.append(r)


for i in range(q):#10**5
    count=0
    target_s=s[l_list[i]-1:r_list[i]]
    print(target_s.count("AC"))


### FIXED CODE ###

n, q=map(int, input().split())
s=input()
l_list=[]
r_list=[]

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 ###

# coding:utf-8

import sys
# from collections import Counter, defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    B = [SI() for _ in range(n)]

    res = 0
    for i in range(n):
        is_good = 1
        for h in range(n):
            for w in range(h + 1, n):
                if B[h][(w + i) % n] != B[w][(h + i) % n]:
                    is_good = 0
                    break

            if not is_good:
                break

        if is_good:
            res += n

    return res


print(main())


### FIXED CODE ###

# coding:utf-8

import sys
# from collections import Counter, defaultdict

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    B = [SI() for _ in range(n)]

    res = 0
    for i in range(n):
        is_good = 1
        for h in range(n):
            for w in range(h + 1, n):
                if B[h][(w + i) % n] != B[w][(h + i) % n]:
                    is_good = 0
                    break

            if not is_good:
                break

        if is_good:
            res += n

    return res


print(main())
### BUGGY CODE ###

N = int(input())
X = input()

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1
if minus < 1:
  minus = 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  n = init_n[i]
  if n != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)
  


### FIXED CODE ###

N = int(input())
X = input()

X_int = int(X, 2)
cnt1 = bin(X_int).count('1')
pcXi01 = cnt1 + 1
pcXi10 = cnt1 - 1
zero_idx = N + 5
if cnt1 == 1:
  for i in range(N):
    if X[i] == '1':
      zero_idx = i

if pcXi10 < 1:
  pcXi10 = 1
Xmod01 = X_int % pcXi01
Xmod10 = X_int % pcXi10

tmp01 = [1]
tmp10 = [-1]
for i in range(N - 1):
  tmp01.append(tmp01[i]*2 % pcXi01)
  tmp10.append(tmp10[i]*2 % pcXi10)

init_n = [0] * N
next_n = [0] * N
for i in range(N):
  if X[i] == '0':
    next_n[i] = (Xmod01 + tmp01[N - 1 - i]) % pcXi01
  else:
    next_n[i] = (Xmod10 + tmp10[N - 1 - i]) % pcXi10

for i in range(N):
  fn = 0
  if i == zero_idx:
    print(0)
    continue

  n = next_n[i]
  fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)
### BUGGY CODE ###

n=int(input())
A=list(map(int,input().split()))
ans = []
for i in range(n):
  ans.append(A[i])
  ans = ans[::-1]
print(*ans)

### FIXED CODE ###

from collections import deque
n=int(input())
A=list(map(int,input().split()))
ans = deque([])
for i in range(n):
  if i % 2 == 0:
    ans.append(A[i])
  else:
    ans.appendleft(A[i])
if n % 2 == 1:
  ans = list(ans)[::-1]
print(*ans)
### BUGGY CODE ###

n = int(input())
items = []
item = tuple(input() for _ in range(n))

for i in range(n):
    if item[i] not in items:
        items.append(item[i])

print(len(items))

### FIXED CODE ###

n = int(input())
items = {}

for i in range(n):
    item = input()
    items[item] = True

print(len(items))