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

def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()
    B = []
    sames = set()

    for a in A:
        isDividable = False
        for b in B:
            if a == b:
                sames.add(b)

            if a % b == 0:
                isDividable = True
                break

        if not isDividable:
            B.append(a)

    print(len(B) - len(sames))


if __name__ == '__main__':
    main()


### FIXED CODE ###

# import collections


def main():
    _ = int(input())
    A = list(map(int, input().split()))

    A.sort()

    # sames = 0
    # C = collections.Counter(A)
    # for v in C.values():
    #     if v > 1:
    #         sames += 1

    a_max = A[-1]
    dp = [0] * (a_max + 1)
    # dp = [True] * a_max
    # A = set(A)

    for a in A:
        if dp[a] != 0:
            dp[a] = 2
            continue

        i = a
        while i < a_max + 1:
            dp[i] += 1
            i += a

    r = 0
    for a in A:
        if dp[a] == 1:
            r += 1

    print(r)

    #     if dp[a - 1]:
    #         tmp_a = a * 2
    #         while tmp_a < a_max + 1:
    #             dp[tmp_a - 1] = False
    #             tmp_a += a

    # r = 0
    # for a in A:
    #     if dp[a - 1]:
    #         r += 1

    # print(r - sames)


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

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
import sys
sys.setrecursionlimit(10**6)
mod=998244353
n=i1() 
d=[]
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
r=[]

for i in range(n):
 r.append(bisect.bisect_left(dx,dx[i]+dd[i]))
class tt():
 def __init__(self):
  self.dt=[0 for i in range(n)]
 def ddd(self,i):
  x=r[i]-1
  for k in range(i+1,r[i]):
      if self.dt[k]==0:
         x=max(x,self.ddd(k))
      else:
         x=max(x,self.dt[k])
  self.dt[i]=x
  return x
ss=tt()
for i in range(n):
  if ss.dt[i]==0:
    ss.ddd(i)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=(dp[i+1]+dp[ss.dt[i]+1])%mod
  
  
print(dp[0]%mod)    

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
l=[]
r=[]
ans = 0
for i in range(q):
    l1,r1=[int(i) for i in input().split()]
    l.append(l1)
    r.append(r1)
for i in range(q):
    for j in range(l[i]-1,r[i]-1):
        if s[j]=='A' and s[j+1]=='C':
            ans += 1
    print(ans)
    ans = 0

### FIXED CODE ###

import bisect

n,q = map(int,input().split())
s = input()
l=[]
r=[]
a = []
c = []
for i in range(q):
    l1,r1 = map(int,input().split())
    l.append(l1)
    r.append(r1)
for i in range(n-1):
    if s[i] + s[i+1] == 'AC':
        a.append(i+1)
        c.append(i+2)
for i in range(q):
    ans = 0
    ans = bisect.bisect_right(c,r[i]) - bisect.bisect_left(a,l[i])
    print(ans)
### BUGGY CODE ###

# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni, sets):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
  
  # ra と rb を結合し、rb の親を ra とする
  sets[ra] = sets[ra] | sets[rb]
  uni[rb] = ra
  return True


##
N, K, L = map(int, input().split())

road = [0]*(N+1)
rail = [0]*(N+1)

road_sets = [0]*(N+1)
rail_sets = [0]*(N+1)

for i in range(1, N+1):
  road[i] = -i
  rail[i] = -i
  road_sets[i] = set([i])
  rail_sets[i] = set([i])

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road, road_sets)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail, rail_sets)

for i in range(1, N+1):
  tmp = road_sets[root(i, road)] & rail_sets[root(i, rail)]
  ans = len(tmp)
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")


### FIXED CODE ###

# 頂点 v の所属するグループを調べる
def root(v, uni):
  if uni[v] < 0:  # v が親の場合
    return v
  else:           # v が子の場合
    uni[v] = root(uni[v], uni)  # 親のrootを調べる
    return uni[v]

# 頂点 a と頂点 b をつなぐ。もともと同じグループのとき、False を返す
def connect(a, b, uni):
  # まずはそれぞれ根の番号に置き換える
  ra = root(a, uni)
  rb = root(b, uni)
  if ra == rb:  # a と b がそもそも同じグループに属しているなら即終了
    return False
	
  # ra を大きなグループにしたいので、逆であれば入れ替える
  if uni[ra] > uni[rb]: # rbの方が要素数が多ければ
    tmp = ra
    ra  = rb 
    rb  = tmp

  # ra と rb を結合し、rb の親を ra とする
  uni[ra] += uni[rb]
  uni[rb] = ra
  return True
      
##
N, K, L = map(int, input().split())

road = [-1]*(N+1)
rail = [-1]*(N+1)

for i in range(K):
  a, b = map(int, input().split())
  connect(a, b, road)

for i in range(L):
  a, b = map(int, input().split())
  connect(a, b, rail)


##
dp = [0]*(N+1)
for i in range(1, N+1):
  dp[i] = (root(i, road), root(i, rail))

dic = {}
for i in range(1, N+1):
  key = dp[i]
  if key not in dic:
    dic[key] = 1
  else:
    dic[key] += 1

for i in range(1, N+1):
  ans = dic[dp[i]]
  if i == N:
    print(ans)
  else:
    print(ans, end=" ")
### BUGGY CODE ###

N,Q = map(int, input().split())
SS = input()
lrq = []
for i in range(N-1):
  if SS[i] == "A" and SS[i+1] == "C":
    lrq.append(1)
  else:
    lrq.append(0)
lrq.append(0)
for _ in range(Q):
  l,r = map(int, input().split())
  l -= 1
  r -= 1
  ans = sum(lrq[l:r+1])
  if lrq[r] == 1:
    ans -= 1
  print(ans)


### FIXED CODE ###

N,Q = map(int, input().split())
SS = input()
lrq = []
for i in range(N-1):
  if SS[i] == "A" and SS[i+1] == "C":
    lrq.append(1)
  else:
    lrq.append(0)
lrq.append(0)
lr = []
lr.append(0)
for i in range(N):
  lr.append(lr[i]+lrq[i])
for _ in range(Q):
  l,r = map(int, input().split())
  l -= 1
  r -= 1
  ans = lr[r+1]-lr[l]
  if lrq[r] == 1:
    ans -= 1
  print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]


def bfs(x, y):
    visited, queue = [], deque([(x, y, 0)])
    max_cost = 0
    while queue:
        px, py, cost = queue.popleft()
        max_cost = max(max_cost, cost)

        candidate = ((px + 1, py), (px - 1, py), (px, py + 1), (px, py - 1))
        visited.append((px, py))
        for cx, cy in candidate:
            if 0 <= cx < W and 0 <= cy < H and not (cx, cy) in visited and maze[cy][cx] == ".":
                queue.append((cx, cy, cost + 1))
    return max_cost


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == ".":
            ans = max(ans, bfs(x, y))

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(input()) for i in range(M)]
m=10**9+7
b=0
ans=[0,1]
for i in range(1,N+1):
    if (i in A) and (i+1 in A):
        print(0)
        exit()
    if i in A:
        ans.append(0)
    else:
        ans.append(ans[-1]+ans[-2])

print(ans[-1] % m)

### FIXED CODE ###

N,M=map(int,input().split())
N=list(range(1,N+1))
for i in range(M):
    N[int(input())-1]=0
m=10**9+7
ans=[0,1]
for i in N:
    if i==0 and i+1==0:
        print(0)
        exit()
    if i==0:
        ans.append(0)
    else:
        ans.append(ans[-1]+ans[-2])

print(ans[-1] % m)
### BUGGY CODE ###

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

def solve(a):
	l = {}
	count = 0
	while 0 == a % 2:
		a //= 2
		count += 1
	else:
		if count:
			l[2] = count

	for n in range(3, a + 1, 2):
		if a == 1:
			return l

		count = 0
		while 0 == a % n:
			a //= n
			count += 1
		else:
			if count:
				l[n] = count
	return l

l = solve(P)
#print(l)

keys = sorted(l, reverse=True)
r = 1
for key in keys:
	if N <= l[key]:
		r *= key ** (l[key] // N)
print(r)


### FIXED CODE ###

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

def solve(a):
	l = {}
	count = 0
	while 0 == a % 2:
		a //= 2
		count += 1
	else:
		if count:
			l[2] = count

	for n in range(3, int(a ** 0.5) + 1, 2):
		if a == 1:
			return l

		count = 0
		while 0 == a % n:
			a //= n
			count += 1
		else:
			if count:
				l[n] = count
	else:
		if 1 != a:
			l[a] = 1
	return l

l = solve(P)
#print(l)

keys = sorted(l, reverse=True)
r = 1
for key in keys:
	if N <= l[key]:
		r *= key ** (l[key] // N)
print(r)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10000000)

def solve():
    N = int(input())
    adj = [list() for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    # path
    goal = N-1
    def rec(prev, cur):
        if cur == goal:
            return [cur]
        for n in adj[cur]:
            if n != prev:
                res = rec(cur,n)
                if res:
                    return res + [cur]
        return None

    path = rec(None, 0)
    path.reverse()
    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    # count
    def rec(prev, cur):
        return sum(rec(cur, n) for n in adj[cur] if n != prev) + 1

    bscore = rec(white,black)
    print('Fennec' if bscore*2 > N else 'Snuke')

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10000000)

def solve():
    N = int(input())
    adj = [list() for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    # path
    goal = N-1
    path = [0]
    candidates = [adj[0][:]]
    while path[-1] != goal:
        while not candidates[-1]:
            candidates.pop()
            path.pop()
        u = candidates[-1].pop()
        candidates.append([n for n in adj[u] if n != path[-1]])
        path.append(u)

    black = path[(len(path)-1)//2]
    white = path[(len(path)-1)//2+1]

    # count
    path = [black]
    candidates = [[n for n in adj[black] if n != white]]
    cnt = 0
    try:
        while True:
            while not candidates[-1]:
                cnt += 1
                candidates.pop()
                path.pop()
            u = candidates[-1].pop()
            candidates.append([n for n in adj[u] if n != path[-1]])
            path.append(u)
    except IndexError:
        pass
    bscore = cnt
    print('Fennec' if bscore*2 > N else 'Snuke')


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

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

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

a=[0]*n
for i in range(1,n+1,1):
    t=g[:]
#    print(t)
    kai = 0
    ok1 = 1
    ok2 = 1
    for j in range(0,i,1):
        if t[j] != j:
            ok1=0
            break
    for j in range(i,0,-1):
        if ok1 == 1:
            break
        if t[0] != j:
            kai += 1
            t.remove(j)
            t.insert(0,j)
    #
    for j in range(i+1,n+1,1):
        if t[j-1] != j:
            ok2=0
            break
    for j in range(i+1,n+1,1):
        if ok2 == 1:
            break
        if t[n-1] != j:
            kai += 1
            t.remove(j)
            t.append(j)
    a[i-1] = kai 

print(min(a)) 





### FIXED CODE ###

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

import math
import sys
import itertools
import numpy as np

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

a = [0]*(n)
for i in range(n):
    a[t[i]-1]=i
lmax =1
length=1

for i in range(1,n):
    if a[i] < a[i-1]:
        length = 1
    else:
        length += 1
        lmax = max(lmax,length)

print(n - lmax)
### BUGGY CODE ###

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

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

lcm_num = lcm(N,M)

X = ["" for i in range(lcm_num)]

for i in range(N):
    tmp = i*lcm_num // N + 1
    X[tmp-1] = S[i]

for i in range(M):
    tmp = i*lcm_num // M + 1
    if X[tmp-1] == "" or X[tmp-1] == T[i]:
        continue
    else:
        print(-1)
        exit()

print(lcm_num)


### FIXED CODE ###

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

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

lcm_num = lcm(N,M)
lN = lcm_num // N
lM = lcm_num // M
gcd_num = lN * lM

for i in range(0,lcm_num,gcd_num):
    if S[i//lN] == T[i//lM]:
        continue
    else:
        print(-1)
        exit()

print(lcm_num)
### BUGGY CODE ###

import sys
import random
N = int(input())
H = [int(x) for x in input().split()]

if N==1:
    print("Yes")
    sys.exit()

K_left=H[1]-H[0]
if K_left<-1:
    print("No")
    sys.exit()
elif K_left == -1 :
    L_left='-'
elif K_left == 0 :
    L_left='0'
else:
    L_left='+'

for i in range(1,N-1):
    K_right=H[i+1]-H[i]    
    if K_right < -1:
        print("No")
        sys.exit()
    elif K_right == -1 :
        L_right='-'
    elif K_right == 0 :
        L_right='0'
    else:
        L_right='+'

    if L_left =='-' and L_right=='-':
        print("No")
        sys.exit()
    if L_left =='0' and L_right=='-':
        if max(H[0:i]) <= H[i]:
            L_left=L_right
            K_left=K_right
        else:
            print("No")
            sys.exit()
    else:
        L_left=L_right
        K_left=K_right
print("Yes")

### FIXED CODE ###

import sys
import random
N = int(input())
H = [int(x) for x in input().split()]

if N==1:
    print("Yes")
    sys.exit()

K_left=H[1]-H[0]
if K_left<-1:
    print("No")
    sys.exit()
elif K_left == -1 :
    L_left='-'
elif K_left == 0 :
    L_left='0'
else:
    L_left='+'
maxH=max(H[1],H[0])
for i in range(1,N-1):
    K_right = H[i+1]-H[i]    
    if K_right < -1:
        print("No")
        sys.exit()
    elif K_right == -1 :
        L_right='-'
    elif K_right == 0 :
        L_right='0'
    else:
        L_right='+'

    if L_left =='-' and L_right=='-':
        print("No")
        sys.exit()
    if L_left =='0' and L_right=='-':
        if maxH <= H[i]:
            L_left=L_right
            K_left=K_right
        else:
            print("No")
            sys.exit()
    else:
        L_left=L_right
        K_left=K_right
        maxH=max(H[i+1],maxH)
print("Yes")
### BUGGY CODE ###

R, G, B ,N = list(map(int, input().split(' ')))

cnt = 0

li = [R, G, B]
li = sorted(li)

_i = N//li[2]

for i in range(_i+1):
    _j = (N - li[2]*i)//li[1] 
    for j in range(_j+1):
        _k = (N - li[2]*i - li[1]*j)//li[0]
        for k in range(_k, _k+1):
            if i*li[2] + j*li[1] + k*li[0] == N:
                cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B ,N = list(map(int, input().split(' ')))

cnt = 0

li = [R, G, B]
li = sorted(li)

_i = N//li[2]
for i in range(_i+1):
    _j = (N - li[2]*i )//li[1]
    for j in range(_j + 1):
        if (N - i*li[2] -  j*li[1])%li[0] == 0:
            cnt += 1

print(cnt)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
lis=[r,g,b]
lis.sort()
cnt=0
for i in range(n//lis[2] + 1):
  for l in range((n-i*lis[2])//lis[1]+1):
    for m in range((n-i*lis[2]-l*lis[1])//lis[0]+1):
      if i*lis[2]+l*lis[1]+m*lis[0] == n:
        cnt+=1
print(cnt)


### FIXED CODE ###

b,r,g,n=map(int,input().split())
ans=0
for i in range(3000//r+1):
    for j in range(3000//g+1):
        if n-j*g-i*r>=0 and (n-j*g-i*r)%b==0:
            ans+=1
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    for j in range(i+1,n+1):
        s=sum(a[i:j])
        b.append(s)

x=0
for i in reversed(range(41)):
    cnt=0
    for j in b:
        if (x+2**i) & j ==(x+2**i):
            cnt+=1
    if cnt>=k:
        x+=2**i
print(x)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=[]
for i in range(n):
    for j in range(i+1,n+1):
        s=sum(a[i:j])
        b.append(s)

x=0
for i in reversed(range(41)):
    cnt=0
    for j in b:
        if (x+2**i) & j ==(x+2**i):
            cnt+=1
    if cnt>=k:
        x+=2**i
print(x)
### BUGGY CODE ###

K, S = map(int, input().split())
res = 0

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                res += 1
                
print(res)

### FIXED CODE ###

K, S = map(int, input().split())
res = 0

for i in range(K+1):
    for j in range(K+1):
            if 0 <= S - (i + j) <= K:
                res += 1
                
print(res)
### BUGGY CODE ###

A = input()

S = [0]
dic = {0:1}

for n in range(1, len(A)+1):
    S.append(S[-1] + (int(A[-n])*(10**(n-1))))
    sm = S[-1] % 2019
    if sm in dic:
        dic[sm] += 1
    else:
        dic[sm] = 1

result = 0

for num in dic:
    n = dic[num]
    result += (n*(n-1)/2)


print(int(result))


### FIXED CODE ###

S = input()
 
res = [0] * 2019
res[0] = 1
 
d = 1
a = 0
 
for c in reversed(S):
    a += int(c) * d
    a %= 2019
    res[a] += 1
    d *= 10
    d %= 2019
 
ans = 0
for r in res:
    ans += r*(r-1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
s=0
for i in range(n-1):
    for j in range(i+1,n):
        s+=l[i]*l[j]
print(s%(10**9+7))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
sum=sum(l)
s=0
for i in range(n):
    s+=l[i]*(sum-l[i])
print(s//2%(10**9+7))
### BUGGY CODE ###

import copy
from heapq import heappop, heapify, heappush
import math
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
F = [int(i) for i in input().split()]
ans = 0
A.sort(reverse=True)
F.sort()
s = []
for i in range(N):
    s.append([A[i]*F[i], A[i], F[i]])
s.sort(reverse=True, key=lambda x: x[0])

def f(l, T):
    cur = 0
    num = 0
    S = copy.deepcopy(l)
    while cur <= K:
        if num == N:
            break
        a, b, c = S[num]
        if a <= T:
            break
        cur += math.ceil((a - T)/c)
        num += 1
    if cur <= K:
        return True
    else:
        return False

ok, ng = s[0][0], -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(s, mid) == True:
        ok = mid
    else:
        ng = mid
print(ok)

### FIXED CODE ###

def main():
    import copy
    from heapq import heappop, heapify, heappush
    import math
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]
    F = [int(i) for i in input().split()]
    ans = 0
    A.sort(reverse=True)
    F.sort()
    s = []
    for i in range(N):
        s.append([A[i]*F[i], A[i], F[i]])
    s.sort(reverse=True, key=lambda x: x[0])

    def f(S, T):
        cur = 0
        num = 0
        while cur <= K:
            if num == N:
                break
            a, b, c = S[num]
            if a <= T:
                break
            cur += math.ceil((a - T)/c)
            num += 1
        if cur <= K:
            return True
        else:
            return False

    ok, ng = s[0][0], -1
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if f(s, mid) == True:
            ok = mid
        else:
            ng = mid
    print(ok)

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

import sys
input = sys.stdin.readline
import math


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def strdiv(X, k, d):
    P = 0
    q = 0
    for i in range(len(X)):
        q <<= 1
        if i == k:
            q |= 1-int(X[i])
        else:
            q |= int(X[i])
        p, q = divmod(q, d)
        # 商
        P <<= 1
        P |= p
    return P, q


def solve(N, X):
    P = [-1 for i in range(N+1)]
    B = sum([1 for a in X if a == "1"])
    
    for k in range(N):
        if X[k] == "0":
            b = (B + 1)
        else:
            b = (B - 1)
        ans = 0
        x = X

        if b == 0:
            print(0)
        else:
            # first step
            p, q = strdiv(x, k, b)
            ans += 1
            x = bin(q)[2:]
            b = sum([1 for a in x if a == "1"])

            # second step (q < N)
            if P[q] == -1:
                r = q
                while r > 0:
                    p, r = strdiv(x, k, b)
                    ans += 1
                    x = bin(r)[2:]
                    b = sum([1 for a in x if a == "1"])
                P[q] = ans
            print(P[q])


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import math


def read():
    N = int(input().strip())
    X = input().strip()
    return N, X


def bitdiv(N:int, X:str, d:int):
    q = 0
    for i in range(N):
        q <<= 1
        q |= int(X[i])
        p, q = divmod(q, d)
    return q


def solve(N, X):
    BP = [0 for i in range(N)]
    BM = [0 for i in range(N)]

    c = X.count("1")
    

    # 2^k mod (c+1) を高速に求める
    qp = bitdiv(N, X, c+1)
    BP[N-1] = 1 % (c+1)
    for i in range(N-2, -1, -1):
        BP[i] = (BP[i+1] * 2) % (c+1)
    
    # 2^k mod (c-1) を高速に求める
    if c > 1:
        qm = bitdiv(N, X, c-1)
        BM[N-1] = 1 % (c-1)
        for i in range(N-2, -1, -1):
            BM[i] = (BM[i+1] * 2) % (c-1)

    for i in range(N):
        q = 0
        ans = 0
        if X[i] == "0":
            # X_i \equiv (X + 2^i)
            q = (qp + BP[i]) % (c+1)
            ans += 1
        elif X[i] == "1" and c > 1:
            # X_i \equiv (X - 2^i)
            q = (qm - BM[i]) % (c-1)
            ans += 1
        else:
            q = 0
            ans = 0
        while q > 0:
            q %= (bin(q).count("1"))
            ans += 1
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))