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

import copy

d,g = map(int,input().split())
P = []
C = []
for i in range(d):
    p,c = map(int,input().split())
    P.append(p)
    C.append(c)

m = []
def score(point = 0, n = 0, now=0, done=[]):
    donecp = copy.deepcopy(done)
    if point >= g:
        m.append(n)
    else:
        pointcp = point
        ncp = n
        for i in range(1,P[now]+1):
            pointcp += 100*(now+1)
            ncp += 1
            if pointcp >= g:
                m.append(ncp)
                break
        donecp.append(now)
        for i in range(d):
            if not i in donecp:
                score(point+P[now]*100*(now+1) + C[now], n + P[now], i, donecp)

for i in range(d):
    done = []
    score(0,0,i,done)

print(min(m))

### FIXED CODE ###

import math
 
d,g = [int(i) for i in input().split()]
P = []
C = []
for i in range(d):
    p,c = [int(i) for i in input().split()]
    P.append(p)
    C.append(c)

# cnt = 0
# def count():
#     global cnt
#     cnt+=1
#     print(cnt)

def flag(point,P,now):
    if point+100*(now+1)*(P-1) >= g: return 1
    elif point+100*(now+1)*P + C[now] >= g: return 2
    else: return 0

m = 10**9
def score(point = 0, n = 0, now=-1, remain = list(range(d))):
    global m
    if m <= n: return
    elif now == -1:
        for i in remain:
            score(point, n, i, remain)
    elif point >= g: m = n
    elif flag(point,P[now],now) == 1:
        n += math.ceil((g-point)/(100*(now+1)))
        if m > n: m = n
    elif flag(point,P[now],now) == 2:
        n += P[now]
        if m > n: m = n
    else:
        if m <= n+P[now]: return
        else:
            remain = remain[:]
            remain.remove(now)
            nxtp = point + P[now]*100*(now+1) + C[now]
            for i in remain:
                score(nxtp, n + P[now], i, remain)

score()
print(m)
### BUGGY CODE ###

S = input()
l = len(S)
d = {l: 0}
for i in range(len(S)):
    s = int(S[i:l])
    d[i] = s%2019
counter = 0
for i in range(len(S)+1):
    for j in range(i+1, len(S)+1):
        if d[j] == d[i]:
            counter += 1
print(counter)

### FIXED CODE ###

from collections import defaultdict
S = input()
l = len(S)
d = {0:0}
mod10n = 1
for i in range(1, len(S)+1):
    s = int(S[l-i])
    d[i] = (d[i-1] + s * mod10n) %2019
    mod10n = (mod10n * 10) % 2019
count_d = defaultdict(int)
for key in d.keys():
    count_d[d[key]] += 1
counter = 0
for key in count_d.keys():
    counter += (count_d[key] * (count_d[key]-1)) //2

print(counter)
### BUGGY CODE ###

n = int(input())
M = 1046527
a = [0 for i in range(M)]
for i in range(n):
    s = input().split(" ")
    num = 0
    p = 1
    for j in range(len(s[1])):
        if s[1][j] == "A":
            num += p * 1
        elif s[1][j] == "C":
            num += p * 2
        elif s[1][j] == "G":
            num += p * 3
        else:
            num += p * 4
        p *= 5
    h1 = num % M
    h2 = h1 + num % (M - 1)
    k = 0
    if s[0][0] == "i":
        while True:
            h = (h1 + k * h2) % M
            if a[h] == 0:
                a[h] = s[1]
                break
            elif a[h] == s[1]:
                break
            else:
                k += 1
    else:
        while True:
            h = (h1 + k * h2) % M
            if a[h] == s[1]:    
                print("yes")
                break
            elif a[h] == 0:
                print("no")
                break
            else:
                k += 1

### FIXED CODE ###

n = int(input())
dic = set()
for i in range(n):
    Cmd, Key = input().split(" ")
    if Cmd == "insert":
	    dic.add(Key)
    else:
        if Key in dic:
	        print("yes")
        else:
            print("no")
### BUGGY CODE ###

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


D = [0]*(10**6+1)
for i in A:
    # ダブってる値は2以上に
    D[i] += 1
U = []
for i in A:
    # 一つしかないものを選ぶ
    if D[i] == 1:
        U.append(i)

T = [False]*(10**6+1)
for i in A:
    # iの2以上の倍数の値はTrueに
    for j in range(i*2, 10**6+1, i):
        T[j] = True

# TがFalseかつDが1の数を数える
ans = 0
for i in U:
    if T[i] == False:
        ans += 1

print(ans)


### FIXED CODE ###

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

cnt = [0] * ((10 ** 6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10 ** 6) + 1)

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0
        
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

import itertools


A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = {}
for _ in range(M):
    x, y, z = map(int, input().split())
    key = str(x) + "&" + str(y)
    if key in m.keys():
        if m[key] < z:
            m[key] = z
    else:
        m[key] = z
A_B = list(itertools.product(range(1, A + 1), range(1, B + 1)))
A_B_sum = list(map(lambda x: x[0] + x[1], (itertools.product(a, b))))
for i in range(len(A_B)):
    # print(str(A_B[i][0]) + "&" + str(A_B[i][1]))
    if str(A_B[i][0]) + "&" + str(A_B[i][1]) in m.keys():
        # print(str(A_B[i][0]) + "&" + str(A_B[i][1]))
        A_B_sum[i] -= m[str(A_B[i][0]) + "&" + str(A_B[i][1])]
print(min(A_B_sum))

### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
min_a = min(a)
min_b = min(b)
ans = min_a + min_b
for _ in range(M):
    i, j, c = map(int, input().split())
    ans = min(ans, a[i - 1] + b[j - 1] - c)
print(ans)
### BUGGY CODE ###

from collections import deque, Counter
from pprint import pprint
MAX_VAL = 10 ** 9
H, W = map(int, input().split())



border_row = "#"*(W+2)
field = [border_row]
c = Counter()
for i in range(H):
    line = input()
    temp_c = Counter(line)
    c += temp_c
    field.append("#"+line+"#")
field.append(border_row)

cost = [[MAX_VAL]*(W+2) for _ in range(H+2)]

if field[1][1] == ".":
    cost[1][1] = 1
else:
    cost[1][1] = MAX_VAL

visited = [[False]*(W+2) for _ in range(H+2)] 
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((1, 1))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if field[ny][nx] == ".":
                cost[ny][nx] = min(cost[ny][nx], cost[y][x]+1)
                if not visited[ny][nx]:
                    q.append((nx, ny))
        visited[y][x] = True

bfs()
# pprint(cost)
# print(cost[H][W])
print(H*W-c["#"]-cost[H][W]) if cost[H][W] < MAX_VAL else print(-1)




### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())


field = []
num_blacks = 0
for i in range(H):
    line = input()
    num_blacks += line.count(".")
    field.append(line)

cost = [[-1]*(W) for _ in range(H)]

cost[0][0] = 1
dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def bfs():
    q = deque()
    q.append((0, 0))
    while len(q):
        x, y = q.popleft()
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if nx < 0 or nx >= W or ny < 0 or ny >= H:
                continue

            if field[ny][nx] == "." and cost[ny][nx] < 0:
                cost[ny][nx] = cost[y][x]+1
                q.append((nx, ny))

bfs()
print(num_blacks - cost[H-1][W-1]) if cost[H-1][W-1] > 0 else print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N = int(input())
G = [set() for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].add(b)
    G[b].add(a)
visited = [False] * N
visited[0] = True


def dfs(v):
    if v == N-1:
        return [N-1]
    for u in G[v]:
        if visited[u]:
            continue
        visited[u] = True
        ret = dfs(u)
        visited[u] = False
        if ret:
            return [v] + ret
    return None


path = dfs(0)
l = len(path)
u, v = 0, 0
if l % 2 == 0:
    u = path[l//2-1]
    v = path[l//2]
else:
    u = path[l//2]
    v = path[l//2+1]
G[u].remove(v)
G[v].remove(u)

uf = UnionFind(N)
for u in range(N):
    for v in G[u]:
        uf.unite(u, v)
fen = 0
snu = 0
for v in range(N):
    if uf.same(v, 0):
        fen += 1
    else:
        snu += 1
if fen > snu:
    print('Fennec')
else:
    print('Snuke')


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)


def dfs(v, dist):
    for u in G[v]:
        if dist[u] != -1:
            continue
        dist[u] = dist[v] + 1
        ret = dfs(u, dist)


dist_fen = [-1] * N
dist_fen[0] = 0
dfs(0, dist_fen)

dist_snu = [-1] * N
dist_snu[N-1] = 0
dfs(N-1, dist_snu)

fen = 0
for v in range(N):
    if dist_fen[v] <= dist_snu[v]:
        fen += 1
if fen > N // 2:
    print('Fennec')
else:
    print('Snuke')
### BUGGY CODE ###

def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

n= int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]

arr = [i for i in arr if i % 2==0]

cnt=0

#1つでも偶数が存在する場合　trueでループ処理対象
#奇数は処理対象外にしてもよい

while len(arr)>0:
    
    if any(x % 4 == 0 for x in arr):

        val=max(list(filter(lambda x : x%4 ==0, arr)))        
        idx=arr.index(val)

        #奇数は計算しなくて良い計算するだけ無駄
        arr=[x*3 for x in arr]
        arr[idx]//=6
    
    elif any(x % 2 == 0 for x in arr):
    
        val=max(list(filter(lambda x : x%2 ==0, arr)))        
        idx=arr.index(val)
        
        #奇数は計算しなくて良い計算するだけ無駄
        arr=[x*3 for x in arr]
        arr.pop(idx)
    cnt+=1

print(cnt)

### FIXED CODE ###

def getinputdata():

    array_result = []    
    array_result.append(input().split(" "))

    flg = True

    try:
        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = True

            else:

                flg = False
    finally:

        return array_result

arr_data = getinputdata()

n= int(arr_data[0][0])

arr=[int(arr_data[1][x]) for x in range(n)]
arr01 = [x for x in arr if x % 4 ==0] 
arr02 = [x for x in arr if x % 4 !=0 and x % 2==0] 

cnt=0
if len(arr)>0:

    for i in arr01:

        while i % 2==0:

            i//=2
        
            cnt+=1
    
    cnt+=len(arr02)
   
print(cnt)
### BUGGY CODE ###

n,k=map(int, input().split())
if k>=n:
    a=[n]*n
    print(*a)
    exit()
a=list(map(int, input().split()))

class segtree:
    x_unit=0 # 要素として入れられる最大値
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[self.x_unit]*(2*self.n)

    def build(self, seq):
        for i,j in enumerate(seq, start=self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = 0
            # セグ木トーナメント表の左右を比較
            # 例えばn=8の時、seq[4]はx[12]に、seq[5]はx[13]に入っている
            # さらにx[14]とx[15]の間に来るのはx[7]、x[12]とx[13]の間に来るのはx[6]

    def fold(self,l,r): # 区間[l, r)値に+1 
        l+=self.n
        r+=self.n-1
        while l<r:
            if l%2==1: # lが奇数
                self.x[l]+=1
                l+=1 # 偶数に調節
            if r%2==0: # rが偶数
                self.x[r]+=1
                r-=1 # 開区間なので1個前は奇数番目の要素
            l //= 2
            r //= 2
        if l==r:
            self.x[l]+=1
        #print(self.x)
    def get(self,i): # seq[i]に対する値を取得 
        i+=self.n
        ret=self.x[i]
        while i>1:
            i //= 2
            ret+=self.x[i]
        return ret

for z in range(k):
    seq=[0]*n
    q=[(max(0, i-a[i]), min(n,i+a[i]+1)) for i in range(n)]
    seg=segtree(n)
    seg.build(seq)
    for i in range(n):
        l,r=q[i]
        seg.fold(l,r)
    ans=[]
    for i in range(n):
        ans.append(seg.get(i))
    a=ans+[]
    if all([i==n for i in a]):
        break
print(*a)

### FIXED CODE ###

n,k=map(int, input().split())
a=list(map(int, input().split()))
from itertools import accumulate
for _ in range(k):
    new=[0]*n
    for i in range(n):
        j=a[i]
        l=max(0,i-j)
        r=min(n-1,i+j)
        new[l]+=1
        if r+1<n:
            new[r+1]-=1
    new=list(accumulate(new))
    a=new
    if all([i==n for i in a]):
        break
print(*a)
### 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

N,M = map(int,input().split())
ans = M//N

if is_prime(M):
    ans = 1
else:
    while M%ans != 0 and ans != 1:
        ans -= 1
print(ans)


### FIXED CODE ###

from bisect import bisect_right

def divisor(n):
    ass = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0:
            ass.append(i)
            if i**2 == n:
                continue
            ass.append(n//i)
    ass.sort()
    return ass 


N,M = map(int,input().split())
a = M//N
c = True

li = divisor(M)

x = bisect_right(li,a)

print(li[x-1])
### BUGGY CODE ###

from time import time
import numpy as np

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    min_costs = [0 for i in range(N)]
    min_costs[1] = abs(h[1] - h[0])


    for i in range(2, N):
        min_cost = 1000000000
        for j in range(1, K+1):
            if i-j < 0: break
            cost = abs(h[i] - h[i-j]) + min_costs[i-j]
            if cost < min_cost:
                min_cost = cost
        min_costs[i] = min_cost

    print(min_costs[N-1])



if __name__ == '__main__':
    start = time()
    main()
    # print(time() - start)



### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    min_costs = [0 for i in range(N)]
    min_costs[1] = abs(h[1] - h[0])


    for i in range(2, N):
        min_cost = 1000000000
        for j in range(1, K+1):
            if i-j < 0: break
            cost = abs(h[i] - h[i-j]) + min_costs[i-j]
            if cost < min_cost:
                min_cost = cost
        min_costs[i] = min_cost

    
    print(min_costs[N-1])



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

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort()
suma = sum(A)
u = 10**12
d = 0
for i in range(50):
    x = (u + d)//2
    s = 0
    for i in range(N):
        f = F[i]
        j = -(i+1)
        a = A[j]
        b = x // f
        s += max(0,a-b)
    if s <= K:
        u = x
    else:
        d = x
print(u)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
A.sort()
F.sort()
suma = sum(A)
u = 10**12
d = 0
for i in range(50):
    x = (u + d)//2
    s = 0
    for i in range(N):
        f = F[i]
        j = -(i+1)
        a = A[j]
        b = x // f
        s += max(0,a-b)
    if s <= K:
        u = x
    else:
        d = x
print(u)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

cur(1)
print(*ans[1:])

### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(*ans[1:])
### BUGGY CODE ###

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

A.sort()

for i in range(M):
    bj, cj = map(int, input().split())
    for j in range(bj):
        if A[j] < cj:
            A[j] = cj
        else:
            break
    A.sort()

print(sum(A))

### FIXED CODE ###

import numpy as np

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

b = [0] * M
c = [0] * M
for i in range(M):
    b[i], c[i] = map(int, input().split())

lst = np.array([c, b]).T.tolist()
lst.sort(reverse=True)
c = np.array(lst).T.tolist()[0]
b = np.array(lst).T.tolist()[1]

k = 0
judge = 0
for i in range(M):
    if k+b[i]-1 < N:
        if A[k+b[i]-1] < c[i]:
            A[k:k+b[i]] = [c[i]] * b[i]
            k += b[i]
        else:
            for j in range(b[i]):
                if k < N:
                    if A[k] < c[i]:
                        A[k] = c[i]
                        k += 1
                    else:
                        judge = 1
                        break
            if judge == 1:
                break
    elif k < N:
        for j in range(b[i]):
            if k < N:
                if A[k] < c[i]:
                    A[k] = c[i]
                    k += 1
                else:
                    judge = 1
                    break
        if judge == 1:
            break
    else:
        break

print(sum(A))
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
for i in range(1,2 ** n):
    s_i = bin(i)[2:].zfill(n)
    tmp = []
    for j in range(n):
        if s_i[j] == '1':
            tmp.append(s[j])
            if s_i[j] in tmp:
                break
    if len(tmp) == len(set(tmp)):
        count += 1

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

### FIXED CODE ###

n = int(input())
s = input()
t = list(set(s))
alpha = {}
for i in range(len(t)):
    alpha[t[i]] = s.count(t[i])

count = 1
for k, v in alpha.items():
    count *= (v + 1)
count -= 1
print(count%(10**9+7))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors
m = [0] * MAX
t = set()
for i in range(n):
  m[a[i]] += 1
  if m[a[i]] == 1:
    t.add(a[i])
  elif m[a[i]] == 2:
    t.discard(a[i])
#print(m[:30])
mx = max(a)
ans = 0
tlen = len(t)
for idx in range(tlen):
  i = t.pop()
  #if m[i] != 1:
    #continue
  divs = make_divisors(i)
  flg = True
  #print('i : ', i)
  #print(divs)
  for j in range(len(divs)):
    div = divs[j]
    if div == i:
      continue
    
    if m[div] > 0:
      flg = False
      break
  if flg:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MAX = 10 ** 6 + 10

one = a.count(1)
if one > 0:
  if one == 1:
    print(1)
  else:
    print(0)
  exit(0)

sieve = [True] * MAX
counts = [0] * MAX
a.sort()
ans = 0
sieve[0] = False
sieve[1] = False
for i in range(n):
  counts[a[i]] += 1
  if not sieve[a[i]]:
    continue
  for j in range(a[i]*2, MAX, a[i]):
    sieve[j] = False
  if counts[a[i]] == 1:
    ans += 1
  elif counts[a[i]] == 2:
    ans -= 1
    
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD=10**9+7
n,k=map(int,input().split())

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
inv_table = [0]+[1]
for i in range(2,k+1):
  inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    #comb1=comb1*(n-i+1)//i
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    #comb2=comb2*(n-i)//i
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

MOD=10**9+7
n,k=map(int,input().split())

def pow_mod(x,n):
  if n==0:
    return 1
  elif n==1:
    return x
  else:
    xn2=pow_mod(x,n//2)
    if n%2==0:
      return (xn2*xn2)%MOD
    else:
      return (xn2*xn2*x)%MOD

def fact_mod(a):
  if a<=1:
    return 1
  else:
    return a*fact_mod(a-1)%MOD
  
def perm_mod(n,a):
  if a==1:
    return n
  else:
    return (n*perm_mod(n-1,a-1))%MOD

def inv_mod(a):
  return pow_mod(a,MOD-2)%MOD
  
def comb_mod(na,fa):
  ainv=inv_mod(fa)
  return (na*ainv)%MOD
  
if k>=n-1:  
  #nHn=(2n-1)Cn
  perm=perm_mod(2*n-1,n)
  fact=fact_mod(n)
  comb=comb_mod(perm,fact)
  #print(perm,fact,comb)
  print(comb)
else:
  inv_table = [0]+[1]
  for i in range(2,k+1):
    inv_table+=[inv_table[MOD%i]*(MOD-int(MOD/i))%MOD]
  
  comb_sum=1
  fact=1
  comb1=1
  comb2=1
  for i in range(1,k+1):
    #comb1=comb1*(n-i+1)//i
    comb1=(comb1*(n-i+1)*inv_table[i])%MOD
    #comb2=comb2*(n-i)//i
    comb2=(comb2*(n-i)*inv_table[i])%MOD
    comb=(comb1*comb2)%MOD
    comb_sum+=comb
  
  print(comb_sum%MOD)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1) % (v + 1)
        if v!=1:
            r[i] += pow(2, n-i-1) % (v - 1)
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1)%(v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1)%(v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()

n= int(input())
a=list(input())

v=a.count('1')

ans=[0]*n
A=[0]*n
# n以下の残り回数を記録
for i in range(n):
    x=i
    cnt=0
    while x>0:
        cnt+=1
        r = 0
        for j in range(19):
            if (x>>j)&1:
                r+=1
            if x>>j==0:
                break
        x=x%r
    ans[i]=cnt

# 各桁をv＋１で割ったあまり
q = [0]*n
# 各桁をv-1で割ったあまり
r = [0]*n
for i in range(n):
    if a[i]=='1':
        if v!=0:
            q[i] = pow(2, n-i-1,v+1) 
        if v!=1:
            r[i] += pow(2, n-i-1,v-1) 
qq=sum(q)
rr=sum(r)

for i in range(n):
    if a[i]=='1':
        if v!=1:
            z = rr - pow(2,n-i-1,v-1)
            cnt = z % (v - 1)
            A[i] = 1 + ans[cnt]
    else:
        z=qq+pow(2,n-i-1,v+1)
        cnt=z%(v+1)
        A[i]=1+ans[cnt]

for i in A:
    print(i)