Harryxun/stf_run huggingface dataset:
import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))

n, m = map(int, input().split())
 
uf = DSU(n)
 
for _ in range(m):
    a, b = map(int, input().split())
    uf.marge(a-1, b-1)
 
ans = 0
 
for i in range(n):
    ans = max(ans, uf.size(i))
 
print(ans)

### FIXED CODE ###

#https://note.nkmk.me/python-union-find/

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

uf = UnionFind(n)

for _ in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = 0

for i in range(n):
    ans = max(ans, uf.size(i))

print(ans)
N,Wmax=map(int,input().split(' '))
info=[ list(map(int,input().split(' '))) for i in range(N) ]
W = info[:][0]
V = info[:][1]

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []

for i in range(N):
	if i==0:
		#重量制限がW[0]以上なら荷物を積むのが最善
		dp.append([ V[0] if W[0]<=w else 0 for w in range(Wmax+1) ])	
	else:
		#今回の重量制限をwとする
		#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
		#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
		#よってこの2つのうち大きいほうをdp[i][w]に採用する
		for w in range(Wmax+1):
			val1 = dp[i-1][w-w[i]]+v[i] 
			val2 = dp[i][w] = dp[i-1][w]
			dp.append(max(val1,val2))
print(dp[N-1][Wmax])

### FIXED CODE ###

N,Wmax=map(int,input().split(' '))
W=[]
V=[]
for _ in range(N):
	w,v = map(int,input().split(' '))
	W.append(w)
	V.append(v)

#dp[i][j]=i番目の品物までだけを選び重量制限をjとしたときの価値の最大値
dp = []
dp.append([0]*min(W[0],Wmax+1)+ [V[0]]*max(0, Wmax+1-W[0]))


for i in range(1,N):
	#今回の重量制限をwとする
	#今回は荷物を積む場合: dp[i][w] = dp[i-1][w-w[i]]+v[i] 
	#今回は荷物を積まない場合: dp[i][w] = dp[i-1][w]
	#よってこの2つのうち大きいほうをdp[i][w]に採用する
	dpi = []
	for j in range(Wmax+1):
		if j<W[i]:
			dpi.append(dp[i-1][j])
		else:
			dpi.append(max(dp[i-1][j], dp[i-1][j-W[i]]+V[i]))
	dp.append(dpi)
print(dp[N-1][Wmax])
l = int(input())
print(pow(1/3,3)

### FIXED CODE ###

l = int(input())
print(pow(l/3,3))
import math

s = input().split()
n = s[0]
k = s[1]

proba = 0

for i in range(1, k):
  n_coin = int(math.log(k/i,2)) + 1
  print(i, n_coin)
  proba += float(1)/n*((0.5)**n_coin)

if n >= k:
	proba += float(n-k+1)/n

### FIXED CODE ###

N, K = list(map(int, input().split()))
 
ans = 0
for i in range(1, N+1):
    p = 1
    x = i
    while x < K:
        p *= 0.5
        x *= 2
    
    ans += p/N
 
print(ans)
a = input()
s = input()
if a >= 3200:
    print(s)
else:
    print("red")

### FIXED CODE ###

a = int(input())
s = input()
if a >= 3200:
    print(s)
else:
    print("red")
x=int(input())
a=int(str(x)[-2:])
b=int(str(x)[:-2])
counter=0
while a>=5:
	a-=5
	counter+=1
while a>=4:
	a-=4
	counter+=1
while a>=3:
	a-=3
	counter+=1
while a>=2:
	a-=2
	counter+=1
while a>=1:
	a-=1
	counter+=1
print(1 if counter<=b else 0)


### FIXED CODE ###

x=int(input())
if x<100:
	print(0)
elif x>=100:
	a=int(str(x)[-2:])
	b=int(str(x)[:-2])
	counter=0
	while a>=5:
		a-=5
		counter+=1
	while a>=4:
		a-=4
		counter+=1
	while a>=3:
		a-=3
		counter+=1
	while a>=2:
		a-=2
		counter+=1
	while a>=1:
		a-=1
		counter+=1
	print(1 if counter<=b else 0)
n, m = map(int, input().split())
li = []
for i in range(m):
    li.append(int(input()))


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = a1 + a2
            a1 = a2
            a2 = a3

        return a3

ans = fib(li[0])

for i in range(m-1):
    ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

ans = ans * fib(n - li[m-1]) % 1000000007
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
li = []
for i in range(m):
    li.append(int(input()))


def fib(dan):
    if dan == 1:
        return 1
    elif dan == 2:
        return 1
    elif dan == 0:
        return 0
    else:
        a1 = 1
        a2 = 1
        a3 = 0
        for _ in range(dan-2):
            a3 = (a1 + a2) % 1000000007
            a1 = a2 % 1000000007
            a2 = a3 % 1000000007

        return a3



if m != 0:
    ans = fib(li[0]) % 1000000007
    for i in range(m-1):
        ans = ans * fib(li[i+1] - li[i] - 1 ) % 1000000007

    ans = ans * fib(n - li[m-1]) % 1000000007
    print(ans)

else:
    print(fib(n+1))
# -*- coding: utf-8 -*-
A,B,C = int(input())
K = int(input())
S = max(A,B,C) #入力された整数の最大のものを選ぶ
L = [A,B,C] #入力された整数のリスト化
L.remove(S)
L = sum(L + S)

### FIXED CODE ###

# -*- coding: utf-8 -*-
A,B,C=map(int,input().split())
K = int(input())
S = max(A,B,C) #入力された整数の最大のものを選ぶ
L = [A,B,C] #入力された整数のリスト化
L.remove(S)
P = sum(L , S*2**K)
print(P)
# A = list(map(int, read().split()))
n = A[-1]
A = A[:3]
A.sort(reverse=True) # descending
ans = 0
if A[1] == A[2] and A[1] == 1: #deal with 1 1
    for i in range(n+1):
        tmp = i*A[0]
        if tmp > n:break
#         print(ans, i, A)
        ans += (n-tmp) - 0 + 1
else :
    for i in range(n+1):
        for j in range(n+1):
            tmp = i * A[0] + j * A[1]
            if tmp > n:break
            tmp = n - tmp
            if tmp % A[2] == 0:
    #             print(i, j, tmp//A[2])
                ans += 1
print(ans)

### FIXED CODE ###

read = input
A = list(map(int, read().split()))
n = A[-1]
A = A[:3]
A.sort(reverse=True) # descending
ans = 0
if A[1] == A[2] and A[1] == 1: #deal with 1 1
    for i in range(n+1):
        tmp = i*A[0]
        if tmp > n:break
#         print(ans, i, A)
        ans += (n-tmp) - 0 + 1
else :
    for i in range(n+1):
        for j in range(n+1):
            tmp = i * A[0] + j * A[1]
            if tmp > n:break
            tmp = n - tmp
            if tmp % A[2] == 0:
    #             print(i, j, tmp//A[2])
                ans += 1
print(ans)
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
X,Y = list(map(int,input().split()))

# a+2b = X
# 2a+b = Y を解く
# -> a = (2Y-X)/3, b = (2X-Y)/3
# (i+1,j+2) の移動が a 回
# (i+2,j+1) の移動が b 回

a = (2*Y-X)/3
b = (2*X-Y)/3 

if not a.is_integer() or not b.is_integer():
    print(0)
    exit(0)

# a回とb回の移動の組み合わせは (a+b)!/a!b!
print(cmb(int(a+b),int(a),mod))

### FIXED CODE ###

mod = 10**9+7

def fact(n):
    ans = 1
    for i in range(2,n+1):
        ans *= i
        ans %= mod
    return ans
    
X,Y = list(map(int,input().split()))

# a+2b = X
# 2a+b = Y を解く
# -> a = (2Y-X)/3, b = (2X-Y)/3
# (i+1,j+2) の移動が a 回
# (i+2,j+1) の移動が b 回

a = (2*Y-X)/3
b = (2*X-Y)/3 

if (X+Y)%3 != 0 or a<0 or b<0:
    print(0)
    exit(0)

# a回とb回の移動の組み合わせは (a+b)!/a!b!
print(fact(int(a+b)) * pow(fact(int(a)),mod-2,mod) * pow(fact(int(b)),mod-2,mod) % mod)
N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A.sort(reverse = True)

dp = [0] + ([-1]*N)
for i in range(1, N+1):
    for a in A:
        if L[a] <= i:
            dp[i] = max(dp[i], dp[i-L[a]] * 10 + a)
    print(dp)
print(dp[-1])

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
L = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
A.sort(reverse = True)

dp = [0] + ([-1]*N)
for i in range(1, N+1):
    for a in A:
        if L[a] <= i:
            dp[i] = max(dp[i], dp[i-L[a]] * 10 + a)
print(dp[-1])
from collections import deque
n, m = map(int, input().split())
route = [[] for i in range(m)]

for i in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b)
    route[b-1].append(a)

next_queue = deque()
sign = [-1] * n

next_queue.append(1)

while next_queue:
    current_number = next_queue.popleft()
    for room in route[current_number - 1]:
        if sign[room - 1] == -1:
            sign[room - 1] = current_number
            next_queue.append(room)
print("Yes")
for i in range(1, n):
    print(sign[i])



### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
route = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b - 1)
    route[b-1].append(a - 1)

next_queue = deque()
sign = [-1 for i in range(n)]
sign[0] = 999

next_queue.append(0)

while next_queue:
    current_number = next_queue.popleft()
    for room in route[current_number]:
        if sign[room] == -1:
            sign[room] = current_number
            next_queue.append(room)
print("Yes")
for i in range(1, n):
    print(sign[i] + 1)
# -*- coding: utf-8 -*-
a, b = map(int, raw_input().split())

if a * b % 2 == 0:
    print "Even"
else:
    print "Odd"




### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, raw_input().split())

if a * b % 2 == 0:
    print "Even"
else:
    print "Odd"
r, D, x = [int(i) for i in input().split()]
i = 1
whie i<=10:
  x = r*x - D
  print(X)
  i += 1	

  

### FIXED CODE ###

r, D, x = [int(i) for i in input().split()]
i = 1
while i<=10:
  x = r*x - D
  print(x)
  i += 1
c=list(map(input().split()))
print(len(set(c)))

### FIXED CODE ###

c=list(input().split())
print(len(set(c)))
S = list(input())
ans = []
count = 0
for i in range(len(S)):
    if S[i]=='A' or S[i]=='T' or S[i]== 'C' or S[i]== 'G':
        count += 1
    else:
        ans.append(count)
        count = 0
print(max(ans))

### FIXED CODE ###

S = list(input())
ans = []
count = 0
for i in range(len(S)):
    if S[i]=='A' or S[i]=='T' or S[i]== 'C' or S[i]== 'G':
        count += 1
        if i == len(S)-1 :
            ans.append(count)
    else:
        ans.append(count)
        count = 0
print(max(ans))
a, b, c, d = map(int, input().split())

alice = []
bob = []
for i in range(a, b+1):
    alice.append(i)
#print(alice)
for j in range(c, d+1):
    bob.append(j)
#print(bob)

combine_alice_bob = alice + bob
#print(combine_alice_bob)
for i in range(len(alice)):
    for j in range(len(bob)):
        if (alice[i]==bob[j] and alice[i+1]==bob[j+1]) or (bob[i]==alice[j] and bob[i+1]==alice[j+1]):
            alice_bob = set(combine_alice_bob)
            print(len(combine_alice_bob)-len(alice_bob)-1)
            exit()

print(0)

### FIXED CODE ###

a, b, c, d = map(int, input().split())

alice = []
bob = []
for i in range(a, b+1):
    alice.append(i)
#print(alice)
for j in range(c, d+1):
    bob.append(j)
#print(bob)

count=0
for i in range(len(alice)):
    if alice[i] in bob:
        count += 1

if count>0:
    print(count-1)
else:
    print(count)
a,b=map(int,input().split())
print("GREATER" if a>b else "LESS" if a<b else "EQUAL")

### FIXED CODE ###

a=int(input())
b=int(input())
print("GREATER" if a>b else "LESS" if a<b else "EQUAL")
# A
N = int(input())
a = list(map(int, input().split()))
flag = True
if N % 3  != 0:
    if max(a) == 0:
        print('Yes')
    else:
        print('No')
else:
    if N == 3:
        if a[0] == a[1] ^ a[2] and a[1] == a[2] ^ a[0] and a[2] == a[0] ^ a[1]:
            print('Yes')
        else:
            print('No')
    else:
        n = int(N /3)
        a = sorted(a)
        for i in range(n):
            tmp_list = a[n * i : n*(i + 1)]
            if min(tmp_list) == max(tmp_list):
                pass
            else:
                flag = False
        if flag:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
flag = True
if max(a) == 0:   # 全て0の時は必ず成り立つ
    flag = True
else:
    if N % 3 != 0:   # 全て0でなくて，Nが3の倍数出ない時は成り立たない
        flag = False
    else:
        n = N // 3
        a_set = set(a)
        if len(a_set) == 2:
            count = [] 
            value = []
            for number in a_set:
                count.append(a.count(number))
                value.append(number)
            if value[0] == 0 and count[0] == n and count[1] == n * 2:
                flag = True
            else:
                flag = False
        elif len(a_set) == 3:
            count = []
            value = []
            for number in a_set:
                count.append(a.count(number))
                value.append(number)
            if count[0] == count[1] == count[2]:
                if value[0] ^ value[1] ^ value[2] == 0:
                    flag = True
                else:
                    flag = False
            else:
                flag = False
        else:
            flag = False
if flag:
    print('Yes')
else:
    print('No')
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(H: int, W: int, s: "List[str]"):
    x=y=0
    k=1 if s[y][x]=="#" else 0
    dt=[[999]*W for _ in range(H)]
    dt[y][x]=1 if s[y][x]=="#" else 0
    for y in range(H):
        for x in range(W):
            if y>0:
                dt[y][x]=min(dt[y][x], dt[y-1][x]+(1 if s[y][x]!=s[y-1][x] else 0))
            if x>0:
                dt[y][x]=min(dt[y][x], dt[y][x-1]+(1 if s[y][x]!=s[y][x-1] else 0))
    print((dt[H-1][W-1]+1)//2)
    #print("#",s,dt)
    """
    for i in range(H+W-2):
        if y<H-1 and s[y][x]==s[y+1][x]:
            y+=1
        elif x<W-1 and s[y][x]==s[y][x+1]:
            x+=1
        else:
            print(x,y,k+1)
            k+=1
            if x<W-1:
                x+=1
            else:
                y+=1
    print(k,(k+1)//2)
    """
    return
        
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)


def solve(H: int, W: int, s: "List[str]"):
    x=y=0
    k=1 if s[y][x]=="#" else 0
    dt=[[999]*W for _ in range(H)]
    dt[y][x]=1 if s[y][x]=="#" else 0
    for y in range(H):
        for x in range(W):
            if y>0:
                dt[y][x]=min(dt[y][x], dt[y-1][x]+(1 if s[y][x]!=s[y-1][x] else 0))
            if x>0:
                dt[y][x]=min(dt[y][x], dt[y][x-1]+(1 if s[y][x]!=s[y][x-1] else 0))
    print((dt[H-1][W-1]+1)//2)
    #print("#",s,dt)
    """
    for i in range(H+W-2):
        if y<H-1 and s[y][x]==s[y+1][x]:
            y+=1
        elif x<W-1 and s[y][x]==s[y][x+1]:
            x+=1
        else:
            print(x,y,k+1)
            k+=1
            if x<W-1:
                x+=1
            else:
                y+=1
    print(k,(k+1)//2)
    """
    return
        
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()
import sys
readline = sys.stdin.readline
 
import numpy as np
from collections import Counter
 

N = int(input())
A = np.array(readline().split())
count = Counter(A)
A = np.array([
    a for a, c in count.items() if c == 1
])
 
if len(A) != 0:
    A = np.sort(A)

i = 0
while True:
    if len(A) == 0:
        break
    pre = A
    a = A[i]
    A = np.delete(A, np.where((A % a == 0) & (A != a)))
    i += 1
    if i >= len(A):
        break

print(len(A))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

import numpy as np
from collections import Counter
from numba import njit




N = int(input())
A = np.array(readline().split(), np.int32)

count = np.zeros((A.max() + 1))
for a in A:
    if count[a] > 1:
        continue
    count[::a] += 1

ret = 0
for a in A:
    ret += count[a] == 1

print(ret)
def main():
    N = int(input())
    v = list(map(int, input().split()))
    v_ki = v[1:N:2].copy()
    val_ki = [i+1 for i in range(10**5)]
    count_ki = [0] * (10**5)
    v_gu = v[0:N:2].copy()
    val_gu = [i+1 for i in range(10**5)]
    count_gu = [0] * (10**5)
    for i in range(N//2):
        count_ki[v_ki[i]] += 1
        count_gu[v_gu[i]] += 1
    
    ki = list(zip(count_ki, val_ki))
    ki.sort()
    ki_len = len(ki)
    gu = list(zip(count_gu, val_gu))
    gu.sort()
    gu_len = len(gu)
    if ki[-1][1] != gu[-1][1]:
        return N-ki[-1][0]-gu[-1][0]
    else:
        return min(N-ki[-2][0]-gu[-1][0], N-ki[-1][0]-gu[-2][0])

if __name__ == "__main__":
    print(main())


### FIXED CODE ###

def main():
    N = int(input())
    v = list(map(int, input().split()))
    v_ki = v[1:N:2].copy()
    val_ki = [i+1 for i in range(10**5)]
    count_ki = [0] * (10**5)
    v_gu = v[0:N:2].copy()
    val_gu = [i+1 for i in range(10**5)]
    count_gu = [0] * (10**5)
    for i in range(N//2):
        count_ki[v_ki[i]-1] += 1
        count_gu[v_gu[i]-1] += 1
    
    ki = list(zip(count_ki, val_ki))
    ki.sort()
    gu = list(zip(count_gu, val_gu))
    gu.sort()
    if ki[-1][1] != gu[-1][1]:
        return N-ki[-1][0]-gu[-1][0]
    else:
        return min(N-ki[-2][0]-gu[-1][0], N-ki[-1][0]-gu[-2][0])

if __name__ == "__main__":
    print(main())
n, a, b = map(int, input())
if (b - a) % 2 == 0:
    print("Alice")
else:
    print("Borys")

### FIXED CODE ###

n, a, b = map(int, input().split())
if (b - a) % 2 == 0:
    print("Alice")
else:
    print("Borys")
from sys import stdin
a = [int(x) for x in list(stdin.readline())]
y = 0

for x in a:
    if x == 1:
        y += 1

print(y)

### FIXED CODE ###

from sys import stdin
a = [int(x) for x in list(stdin.readline().rstrip())]
y = 0

for x in a:
    if x == 1:
        y += 1

print(y)
import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

pc = X.count("1")

# X == 0 の時
if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        mod_s += pow(2, b, sml)
        mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1

# print(mod_s, mod_b, sml, big)


ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml
        ELE.append((t, 1))
    b += 1


def solve(x, c):
    if x == 0:
        return c

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

print("\n".join(map(str, ANS[::-1])))



### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

pc = X.count("1")

# X == 0 の時
if pc == 0:
    for i in range(N):
        print(1)
    exit()

sml = pc - 1
big = pc + 1

b = 0
mod_s = 0
mod_b = 0
for x in X[::-1]:
    if x == "1":
        if sml:
            mod_s += pow(2, b, sml)
            mod_s %= sml

        mod_b += pow(2, b, big)
        mod_b %= big

    b += 1

# print(mod_s, mod_b, sml, big)


ELE = []

b = 0
for x in X[::-1]:
    if x == "0":
        t = (mod_b + pow(2, b, big)) % big
        ELE.append((t, 1))
    else:
        t = (mod_s - pow(2, b, sml)) % sml if sml else 0

        if sml:
            ELE.append((t, 1))
        else:
            ELE.append((0, 0))
    b += 1


def solve(x, c):
    if x == 0:
        return c

    b = 0
    nx = x
    while nx > 0:
        b += nx & 1
        nx >>= 1

    ret = solve(x % b, c + 1)
    return ret


ANS = []
for x, pc in ELE:
    ANS.append(solve(x, pc))

print("\n".join(map(str, ANS[::-1])))
bingo_list = [list(map(int,input().split())) for i in range(3)]
bingo_list = sum(bingo_list,[])
n = int(input())
bingo_number = [int(input())for i in range(n)]
check_list = [0 for i in range(9)]

for j in bingo_number:
    if j in bingo_list:
        check_list[bingo_list.index(j)] = 1

if [1,1,1] in [check_list[:3],check_list[3:6],check_list[6:],check_list[0:7:3],check_list[1:8:3]check_list[2:9:3],check_list[0:9:4],check_list[2:8:2]]:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

bingo_list = [list(map(int,input().split())) for i in range(3)]
bingo_list = sum(bingo_list,[])
n = int(input())
bingo_number = [int(input())for i in range(n)]
check_list = [0 for i in range(9)]

for j in bingo_number:
    if j in bingo_list:
        check_list[bingo_list.index(j)] = 1

if  [1,1,1]  in [check_list[:3], check_list[3:6], check_list[6:], check_list[0:7:3], check_list[1:8:3],check_list[2:9:3],check_list[0:9:4],check_list[2:7:2]]:
    print('Yes')
else:
    print('No')
N = int(input())
a = list(map(int, input().split()))
bol = 0
count =0

while(1):
    for num  in a:
		if num  % 2 == 1:
		    bol = 1

    if bol == 0:
		a = [ i	/2 for i in a]
		count += 1
    else :
		break

print(count)

### FIXED CODE ###

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

while(1):
  for num  in a:
    if num  % 2 == 1:
      bol = 1

  if bol == 0:
        a = [ i	/2 for i in a]
        count += 1
  else:
          break

print(count)