Harryxun/stf_run huggingface dataset:
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())
f_uf = UnionFind(self, N)
for _ in range(M):
  a, b = map(int, input().split())
  f_uf.union(a-1, b-1)
answer = 1
for i in range(N):
  answer = max(answer, f_uf.size(i))
print(answer)

### FIXED CODE ###

from collections import deque

N, M = map(int, input().split())
friends = [[] for _ in range(N+1)]
for __ in range(M):
  a, b = map(int, input().split())
  friends[a].append(b)
  friends[b].append(a)
checked = [0 for ___ in range(N+1)]
answer = 1
for i in range(1, N+1):
  friend = deque(friends[i])
  cnt = 0
  while(len(friend) > 0):
    f = friend.popleft()
    if checked[f] != 0:
      continue
    else:
      checked[f] = 1
      cnt += 1
      for ff in friends[f]:
        friend.append(ff)
  answer = max(answer, cnt)
print(answer)
def Ii():return int(input())
def Mi():return map(int,input().split())
def Li():return list(map(int,input().split()))

n = Ii()%10
if n == 3
  print('bon')
elif n==2 or n == 4 or n == 5 or n==7 or n == 9
  print('hon')
else
  print('pon')

 

### FIXED CODE ###

def Ii():return int(input())
def Mi():return map(int,input().split())
def Li():return list(map(int,input().split()))
 
n = Ii()%10
if n == 3:
  print('bon')
elif n==2 or n == 4 or n == 5 or n==7 or n == 9:
  print('hon')
else:
  print('pon')
import heapq
N,M = map(int, input().split())
A = list(map(int, input().split()))
BC = []

for i in range(M):
    BC.append(list(map(int, input().split())))

BC.sort(key=lambda x: x[1], reverse=True)
A_min = min(A)
heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        if BC[i][1] > min(A):
            heapq.heappush(A,BC[i][1])
            heapq.heappop(A)

    A_min = min(A)

print(sum(A))

### FIXED CODE ###

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

L_max = max(L)
R_min = min(R)

result = R_min - L_max + 1

if result < 0:
    print(0)
else:
    print(result)
n=int(input())
p=list(map(in,input().split()))
t=list(range(1,n+1))
cnt=0
for pp in p:
  for tt in t:
    if pp!=tt:
      cnt+=1
print('Yes' if 0<=cnt<=2 else 'No')

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
t=list(range(1,n+1))
cnt=0
for i in range(n):
  if p[i]!=t[i]:
    cnt+=1
print('YES' if 0<=cnt<=2 else 'NO')
s=input()
if s=='Sunny':
    print('Cloudy')
elif s=='Cloudy':
    print('Rainy')
else s=='Rainy':
    print('Sunny')


### FIXED CODE ###

s=input()
if s=='Sunny':
    print('Cloudy')
elif s=='Cloudy':
    print('Rainy')
elif s=='Rainy':
    print('Sunny')
A, B = map(int, input().split())
C = -(-A//0.08)
D = -(-(A+1)//0.08)
for i in range(C,D):
    if i//10 == B:
      print(i)
      break
else:
    print(-1)

### FIXED CODE ###

A, B = map(int, input().split())
C = int(-(-A//0.08))
D = int(-(-(A+1)//0.08))
for i in range(C,D):
    if i//10 == B:
      print(i)
      break
else:
    print(-1)
i = lambda: int(input())
print(len(set([i(), i(), i()])))


### FIXED CODE ###

print(len(set((int(i) for i in input().split()))))
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ab_total_list = []
total_list = []

A.sort()
A.reverse()
if len(A) > K:
    A = A[0:K+1]

B.sort()
B.reverse()
if len(B) > K:
    B = B[0:K+1]

C.sort()
C.reverse()
if len(C) > K:
    C = C[0:K+1]

for i in A:
    for j in B:
        ab_total_list.append(i+j)

ab_total_list.sort()
ab_total_list.reverse()
if len(ab_total_list) > K:
    ab_total_list = ab_total_list[0:K+1]
    
z = 0
min_total = 0
if K > len(ab_total_list):
    min_total = ab_total_list[-1]
else:
    min_total = ab_total_list[K]

for i in ab_total_list:
    for j in C:
        total = i + j
        total_list.append(i+j)

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])

### FIXED CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

ab_total_list = []
total_list = []

A.sort()
A.reverse()
if len(A) > K:
    A = A[0:K+1]

B.sort()
B.reverse()
if len(B) > K:
    B = B[0:K+1]

C.sort()
C.reverse()
if len(C) > K:
    C = C[0:K+1]

ab_total_list = []
for i in A:
    for j in B:
        ab_total_list.append(i+j)

ab_total_list.sort()
ab_total_list.reverse()
if len(ab_total_list) > K:
    ab_total_list = ab_total_list[0:K+1]

for i in range(0, K):
    for j in range(0, int(K/(i+1))):
        if j >= len(C) or i >= len(ab_total_list):
            break
        total = ab_total_list[i] + C[j]
        total_list.append(total)
        if (i*j) > K:
            break

total_list.sort()
total_list.reverse()
for i in range(0, K):
    print(total_list[i])
N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

from collections import Counter
from math import factorial

c = Counter(s)
keys, values = zip(*c.most_common())
#print(keys)
#print(values)
ans = 0
n = 0
for i in range(len(values)):
    if values[i] > 1:
        n = values[i]
        ans += factorial(n) / factorial(2) / factorial(n - 2)
        
print(int(ans))

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

from collections import Counter

c = Counter(s)
keys, values = zip(*c.most_common())
#print(keys)
#print(values)
ans = 0
n = 0
for i in range(len(values)):
    if values[i] > 1:
        n = values[i]
        ans += n*(n-1)//2
        
print(ans)
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    ans = 1
    A.sort()
    A = dq(A)

    print(type(A))

    while A:
        start = A.popleft()
        if not A:
            break
        ans += 1
        A = dq([a for a in A if a % start != 0])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = np.array([int(i) for i in input().split()])

    max_dp = np.max(A) + 1
    dp = np.zeros(max_dp, dtype="int32")

    for a in A:
        if dp[a] >= 2:
            continue
        fancy = np.arange(a, max_dp, a)
        dp[fancy] += 2
        dp[a] -= 1
    print(np.sum(dp == 1))


if __name__ == '__main__':
    main()
a,b,c = input().split()
d = a+b+c
print("YES") if d % 4 == 0 else print("NO")

### FIXED CODE ###

a,b,c = input().split()
d = int(a+b+c)
print("YES") if d % 4 == 0 else print("NO")
a,b = (int(x) for x in input().split())

if a > b:
  print("a > b")
elif a < b:
  print("a < b")
else
  print("a == b")


### FIXED CODE ###

a,b = (int(x) for x in input().split())
 
if a > b:
  print("a > b")
elif a < b:
  print("a < b")
else:
  print("a == b")
a,b,c,d=map(int, input().split())

if a.isdigit() and b.isdigit() and  c.isdigit() and d.a.isdigit():
    if 1<=a<=100 and 1<=b<=100 and 1<=c<=100 and 1<=d<=100:
        if (abs(a-b))>=d and (abs(b-c))>=d:
            print("Yes")
        else:
            print("No")


### FIXED CODE ###

a,b,c,d = map(int,input().split())
print("Yes" if abs(a-c)<=d  or  (abs(a-b)<=d and abs(b-c)<=d) else 'No')
int_n = int(input())

ar_int_a = []
for i in range(int_n):
    ar_int_a.append(int(input()))

numbers = set(ar_int_a)

# written = [i for i in numbers if ar_int_a.count(i) % 2 == 1]
written = len((i for i in numbers if ar_int_a.count(i) % 2 == 1))

# print(len(written))
print(written)

### FIXED CODE ###

from collections import defaultdict


int_n = int(input())

counter = defaultdict(int)

for i in range(int_n):
    counter[int(input())] += 1

written = 0
for c in counter.values():
    if c % 2 == 1:
        written += 1


print(written)
N, M = list(map(int, input().split()))
G = [[] for _ in range(N+1)]
x = [None] * (N+1)

def fail():
    print("No")
    exit()

def dfs(s):
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            dfs(t)
        else:
            if x[t] != x[s] + d:
                fail()

for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1].append([R-1,  D])
    G[R-1].append([L-1, -D])

for i in range(N):
    if x[i] is None:
        x[i] = 0
        dfs(i)

print("Yes")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200002)

N, M = map(int, input().split())
G = [[] for _ in range(N)]
x = [None] * (N)

def dfs(s):
    global x, G
    for t, d in G[s]:
        if x[t] is None:
            x[t] = x[s] + d
            if not dfs(t):
                return False
        else:
            if x[t] != x[s] + d:
                return False
    return True

for _ in range(M):
    L, R, D = map(int, input().split())
    G[L-1].append([R-1,  D])
    G[R-1].append([L-1, -D])

ans = True
for i in range(N):
    if x[i] is None:
        x[i] = 0
        ans &= dfs(i)

print("Yes" if ans else "No")
n = int(input())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

ans = 0
for i in range(n-1):
  if a[i] + 1 == a[i+1]:
    ans += c[i]
  
print(ans + sum(b))  

### FIXED CODE ###

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

ans = 0
for i in range(n - 1):
    if a[i] + 1 == a[i + 1]:
        ans += c[a[i]-1]

print(ans + sum(b))
N,K = map(int,input().split())
A = list(map(int,input().split()))
visited = []
search = set()
now = 1#最初の街にいる
next_town = A[now-1]
count = 1
while(count<=N):
    if next_town in search:#もし次の街が訪れたことがある場合
        break#ループするので抜け出す
    visited.append(now)#今いる街は訪れたこととなるので記録する
    search.add(now)
    next_town = A[now-1]#次に行く街を探す
    now = next_town#次の街に着いたこととして変数を代入
    count += 1

first_roop_city = A[visited[-1]-1]#最初にループした街
first_roop_city_index = visited.index(first_roop_city)#何回目のテレポートにループが始まったか
if K <= len(visited):
    print(visited[K])
else:
    visited = visited[first_roop_city_index:]
    L = len(visited)
    print(visited[(K-first_roop_city_index)%L])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
visited = []
search = set()
now = 1#最初の街にいる
next_town = A[now-1]
count = 1
while(count<=N):
    if next_town in search:#もし次の街が訪れたことがある場合
        break#ループするので抜け出す
    visited.append(now)#今いる街は訪れたこととなるので記録する
    search.add(now)
    next_town = A[now-1]#次に行く街を探す
    now = next_town#次の街に着いたこととして変数を代入
    count += 1

first_roop_city = A[visited[-1]-1]#最初にループした街
first_roop_city_index = visited.index(first_roop_city)#何回目のテレポートにループが始まったか
if K < len(visited):
    print(visited[K])
else:
    visited = visited[first_roop_city_index:]
    L = len(visited)
    print(visited[(K-first_roop_city_index)%L])
n = int(input())
A = list(map(int,input().split()))

c = 0
while all (a%2==0 for a in A):
    A = list(a//2 for a in A)
    c += 1
print(c)

### FIXED CODE ###

print(input().count('1'))
def main ():
N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    return

prod = 1
for a in A:
    prod *= a
    if prod > 1000000000000000000:
        print(-1)
        return

    print(prod)
main ()


### FIXED CODE ###


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

    if 0 in A:
        print(0)
        return

    prod = 1
    for a in A:
        prod *= a
        if prod > 1000000000000000000:
            print(-1)
            return

    print(prod)
    return

main ()
import numba
from numba import njit
i8 = numba.int64


@njit((i8, ), cache=True)
def main(n, m):

    A = []
    B = []
    cnt = 0
    ans = 0

    for _ in range(n):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    while cnt < m:
        A_min = min(A)
        A_min_index = A.index(A_min)
        if cnt + B[A_min_index] < m:
            ans += A_min * B[A_min_index]
            cnt += B[A_min_index]
            A.pop(A_min_index)
            B.pop(A_min_index)
        else:
            for i in range(B[A_min_index]):
                if cnt == m:
                    break
                ans += A_min
                cnt += 1

    print(ans)


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

main(n, m)


### FIXED CODE ###

n, m = map(int, input().split())
drink = sorted([list(map(int, input().split())) for _ in range(n)])

ans = 0

for a,b in drink:
    ans += a*min(b,m)
    m -= min(b,m)
    if m == 0:
        break

print(ans)
S = input()

def dfs(a,s,n): #a:今まで計算した分、s:数字(文字)、n:左から何番目の位置に+を入れるか入れないか
    if(len(s) == n+1):
        return int(s[len(s)-1]) + int(s[:len(s)-1]) + int(s) + 2*a
    else:
        return dfs(a,s,n+1) + dfs(a+int(s[:n]),s[n:],1)

print(dfs(0,S,1))

### FIXED CODE ###

S = input()

def dfs(a,s,n): #a:今まで計算した分、s:数字(文字)、n:左から何番目の位置に+を入れるか入れないか
    if(len(s) == 1):
        return int(s)
    elif(len(s) == n+1):
        return int(s[len(s)-1]) + int(s[:len(s)-1]) + int(s) + 2*a
    else:
        return dfs(a,s,n+1) + dfs(a+int(s[:n]),s[n:],1)

print(dfs(0,S,1))
n = input()
dl = list(map(int,input().split()))
dl.sort()

if n % 2 != 0:
  print(0)
  exit()

  
left = dl[(n//2)-1]
right = dl[(n//2)]

print(right-left)


### FIXED CODE ###

n = int(input())
dl = list(map(int,input().split()))
dl.sort()

if n % 2 != 0:
  print(0)
  exit()

  
left = dl[(n//2)-1]
right = dl[(n//2)]

print(right-left)
N,M=map(int,input().split())
a=list(map(int,input().split()))

A=sum(a)
if N-A<0:
  print(-1)
else :
    print(N-A)


### FIXED CODE ###

R=float(input())

print(R*2*3.141592)
# coding: utf-8

# https://atcoder.jp/contests/abc089/tasks/abc089_d
# 17:17-18:12 done


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L, R = [None] * Q, [None] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())
        L[i] -= 1  # 1-index => 0-index
        R[i] -= 1  # 1-index => 0-index

    positions = [None] * (H*W)
    for i in range(H):
        for j in range(W):
            positions[A[i][j]-1] = (i, j)

    n_graph = D if D <= (H*W)//2 else (H*W)-D

    graphs = [[] for _ in range(n_graph)]

    for start in range(n_graph):
        cost = 0
        start_x, start_y = positions[start]
        m = 0
        while start + m*D < H*W:
            to_x, to_y = positions[start + m*D]
            cost += abs(to_x-start_x) + abs(to_y-start_y)
            graphs[start].append(cost)
            start_x, start_y = to_x, to_y
            m += 1
        
    for l, r in zip(L, R):
        graph_num = l % n_graph
        graph = graphs[graph_num]
        print(graph[r//n_graph] - graph[l//n_graph])


main()
# print(main())


### FIXED CODE ###

# coding: utf-8

# https://atcoder.jp/contests/abc089/tasks/abc089_d
# 17:17-18:17 read testcase
# 18:17-18:26 done


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = list(map(int, input().split()))
    Q = int(input())
    L, R = [None] * Q, [None] * Q
    for i in range(Q):
        L[i], R[i] = map(int, input().split())
        L[i] -= 1  # 1-index => 0-index
        R[i] -= 1  # 1-index => 0-index
    
    if D == H*W:
        for _ in range(Q):
            print(0)
        return None

    positions = [None] * (H*W)
    for i in range(H):
        for j in range(W):
            positions[A[i][j]-1] = (i, j)

    n_graph = D if D <= (H*W)//2 else (H*W)-D

    graphs = [[] for _ in range(n_graph)]

    for start in range(n_graph):
        cost = 0
        start_x, start_y = positions[start]
        m = 0
        while start + m*D < H*W:
            to_x, to_y = positions[start + m*D]
            cost += abs(to_x-start_x) + abs(to_y-start_y)
            graphs[start].append(cost)
            start_x, start_y = to_x, to_y
            m += 1

    for l, r in zip(L, R):
        graph_num = l % n_graph
        graph = graphs[graph_num]
        print(graph[r//D] - graph[l//D])


main()
# print(main())
ef to_fizzbuzz(number):
    if number % 15 == 0:
        return 'FizzBuzz'

    if number % 3 == 0:
        return 'Fizz'

    if number % 5 == 0:
        return 'Buzz'

    else:
        return str(number)
        # return i

def main():
    N = int(input())
    # FizzBuzz含む文字列
    fblist = []
    for number in range(1, 10**6):
        result = to_fizzbuzz(number)
        fblist.append(result)

        # print(fblist)

    # Ｎ項目までの数列
    n_list = fblist[0:N]
    # Ｎ項まで　かつ　数字のみの数列

    n_numlist = []

    for s in n_list:
        if s.isdigit() == True:
            n_numlist.append(int(s))

    print(sum(n_numlist))

main()

### FIXED CODE ###

def to_fizzbuzz(number):
    if number % 15 == 0:
        return 'FizzBuzz'

    if number % 3 == 0:
        return 'Fizz'

    if number % 5 == 0:
        return 'Buzz'

    else:
        return str(number)
        # return i

def main():
    N = int(input())
    # this list concludes "FizzBuzz", "Fizz" or "Buzz"
    fblist = []
    for number in range(1, 10**6):
        result = to_fizzbuzz(number)
        fblist.append(result)

    # the list up to N
    n_list = fblist[0:N]
    # this list contains only numbers and up to N

    n_numlist = []

    for s in n_list:
        if s.isdigit() == True:
            n_numlist.append(int(s))

    print(sum(n_numlist))


main()
# http://www.deqnotes.net/acmicpc/p0006/
import re
import numpy as np

def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1
    coin_values=np.array(coin_values)
    coin_nums=np.array(coin_nums)
    all = np.dot(coin_values, coin_nums)
    oturi = all - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)

    # 2.
    for i in reversed(range(0,len(coin_values))):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])

    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))

if __name__ == "__main__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)

### FIXED CODE ###

import math
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)
 
    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])
 
    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
 
if __name__ == "__main__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500?????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
s = int(input())
array = []
cnt = 1
array.append(s)
while True:
    s = cal(s)
    array.append(s)
    if array[cnt] in array[:cnt]:
        print(cnt +1)
        break
    cnt += 1

### FIXED CODE ###

def cal(s):
    if s % 2 == 0:
        return int(s/2)
    else:
        return s * 3 + 1


s = int(input())
array = []
cnt = 1
array.append(s)
while True:
    s = cal(s)
    array.append(s)
    if array[cnt] in array[:cnt]:
        print(cnt +1)
        break
    cnt += 1
n = int(input())
s = input()
x = int(s, 2)
p = popcount(x)

def popcount(x):
	'''xの立っているビット数をカウントする関数
	(xは64bit整数)'''

	# 2bitごとの組に分け、立っているビット数を2bitで表現する
	x = x - ((x >> 1) & 0x5555555555555555)

	# 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
	x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

	x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
	x = x + (x >> 8) # 16bitごと
	x = x + (x >> 16) # 32bitごと
	x = x + (x >> 32) # 64bitごと = 全部の合計
	return x & 0x0000007f

nxt = [i for i in range(n+1)]
for i in range(1, n):
	nxt[i] %= popcount(i)

for i in range(n):
	ans = 0
	tmp = x ^ (1 << (n-1-i))
	if tmp == 0:
		print(0)
		continue
	if tmp > x:
		ans = 1
		tmp %= p+1
	else:
		ans = 1
		tmp %= p-1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)

### FIXED CODE ###

n = int(input())
s = input()
x = int(s, 2)
p = s.count("1")
if p > 1:
	pre0 = x%(p-1)
pre1 = x%(p+1)

nxt = [i for i in range(n+10)]
for i in range(1, n+10):
	nxt[i] %= bin(i).count("1")

for i in range(n):
	if x == 1<<(n-1-i):
		print(0)
		continue
	if s[i] == "0":
		tmp = (pre1 + pow(2, n-1-i, p+1)) % (p+1)
	else:
		tmp = (pre0 - pow(2, n-1-i, p-1)) % (p-1)
	ans = 1
	while tmp > 0:
		ans += 1
		tmp = nxt[tmp]
	print(ans)
from math import floor,ceil
x = input().split()
a = int(x[0])
b = int(x[1])
c = int(x[2])
print(floor(floor(a*c/b)-a*floor(c/b)))


### FIXED CODE ###

k = int(input())
x = input().split()
a = int(x[0])
b = int(x[1])
c = 0
for i in range(a,b+1):
  if i%k==0:
    c = 1
    break
if c==1:
  print("OK")
else:
  print("NG")
x, y = (int(s) for s in input().split())
while y > 0
    x, y = y, x % y
print(x)

### FIXED CODE ###

x, y = (int(s) for s in input().split())
while y > 0:
    x, y = y, x % y
print(x)
import math
n=input()
A=0
def is_prime(m):
 for i in range(2, int(math.sqrt(m))+1):
  if m%i==0:
   return False
  return True
for i in range(n):
 k=input()
 if is_prime(k):
 A+=1
print A

### FIXED CODE ###

import math
n=input()
A=0
def is_prime(m):
 for i in range(2, int(math.sqrt(m))+1):
  if m%i==0:
   return False
 return True
for i in range(n):
 k=input()
 if is_prime(k):
  A+=1
print A