Harryxun/stf_run huggingface dataset:
N = map(int,input().split())

f = sum(list(map(int,str(N))))

if N % f == 0:
print("Yes")
else:
print("No")


### FIXED CODE ###

N = int(input())
f = sum(map(int,list(str(N))))

if N % f == 0:
        print("Yes")
else:
        print("No")
print 1110 - input

### FIXED CODE ###

print(1110-int(input()))
# from math import gcd
import math
N = int(input())
A = list(map(int,input().split()))
# N=3
# A=[12 ,15 ,18]
l=[0]*N
r=[0]*N
l[0]=A[0]
r[0]=A[N-1]
for i in range(1,N-1):
    l[i]=math.gcd(l[i-1],A[i])
    r[i]=math.gcd(r[i-1],A[N-1-i])    
gcdlist = [l[N-2],r[N-2]]
for i in range(N-2):
    gcdlist.append(math.gcd(l[i],r[N-3-i]))
# print(gcdlist)
print(max(gcdlist))

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
# N=3
# A=[12 ,15 ,18]
l=[0]*N
r=[0]*N
l[0]=A[0]
r[0]=A[N-1]
for i in range(1,N-1):
    l[i]=gcd(l[i-1],A[i])
    r[i]=gcd(r[i-1],A[N-1-i])    
gcdlist = [1,l[N-2],r[N-2]]
for i in range(N-2):
    gcdlist.append(gcd(l[i],r[N-3-i]))
#print(gcdlist)
print(max(gcdlist))
import numpy as np
import sys

input = sys.stdin.readline

S = input()

S = sorted(S[:-1])

alpha = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']


s = 0
for t in S:
    if t == alpha[s] :
        s+=1


if s == len(alpha):
    print("None")
else:
    print(alpha[s])

### FIXED CODE ###

import numpy as np
import sys

input = sys.stdin.readline

S = input()

S = sorted(list(set(S[:-1])))


alpha = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']


j = 0
for i in range(len(alpha)):
    if  S[j]== alpha[i] :
        if len(S)-1 != j:j+=1
    else:
        print(alpha[i])
        exit()


print("None")
A,B = map(int,input().split())

print(solver(B) ^ solver(A-1))

def solver(N)
  if N % 2 == 1:
    return oddodd(N)
  else:
    return N+1 ^ oddodd(N+1)

def oddodd(N)
  return 1 if (N+1)/2 % 2 == 1 else 0 

### FIXED CODE ###

def solver(N):
  if N % 2 == 1:
    return oddodd(N)
  else:
    return (N+1) ^ oddodd(N+1)

def oddodd(N):
  return 1 if (N+1)/2 % 2 == 1 else 0 

A,B = map(int,input().split())

print(solver(B) ^ solver(A-1))
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num)
    
    return cnt


while True:
    mid = (left + right) // 2
    tmp = count(mid)
    if tmp == K:
        break
    elif tmp > K:
        if left == mid:
            mid += 1
            break
        left = mid
    else:
        right = mid

if mid == 0:
    print(mid)
    exit()

right = mid
while True:
    tmp = count(mid)
    if tmp == K and tmp != count(mid-1):
        print(mid)
        break
    elif tmp == K:
        right = mid
    else:
        left = mid
    mid = (left + right) // 2

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt

while True:
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        exit()
    tmp = count(mid)
    if right - left <= 1:
        mid = right
        break
    elif tmp > K:
        left = mid
    else:
        right = mid

right = mid

while True:
    tmp = count(mid)
    if right - left <= 1:
        print(right)
        break
    elif tmp == K:
        right = mid
    else:
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break
n = int(input())
data = list(input().rstrip())
cnt = 0

if data.count(data[0]) == n:
	print(1)
	exit()

for i in range(0,len(data)):
	cnt = 0
	for j in range(i+1,len(data)):
		if data[i] == data[j]:
			cnt += 1
		else:
			break
	if cnt >= 1:
		print(i+1,j,data)
		del data[i+1:j]
print(len(data))
print(data)

### FIXED CODE ###

n = int(input())
data = list(input().rstrip())
ans = [data[0]]
cnt = 0
i = 0

for _ in range(n):
  if ans[-1] != data[i]:
    ans.append(data[i])
  i += 1
    
print(len(ans))
A = input()
B = input()
C = input()
flag = 'A'

def chk(A, B, C, flag, st):
    if len(st) == 0:
        return flag
    elif st[0].upper() == flag:
        if flag == 'A':
            A = st[1:]
            st = A
        elif flag == 'B':
            B = st[1:]
            st = B
        elif flag == 'C':
            C = st[1:]
            st = C
    elif st[0] == 'a':
        flag = 'A'
        st = A[1:]
    elif st[0] == 'b':
        flag = 'B'
        st = B[1:]
    elif st[0] == 'c':
        flag = 'C'
        st = C[1:]
    return chk(A, B, C, flag, st)

print(chk(A, B, C, flag, st=A))

### FIXED CODE ###

dic = {s:list(input()) for s in 'abc'}

flag = 'a'
while dic[flag]:
  flag = dic[flag].pop(0)
print(flag.upper())
s = input()
s_len = len(s)
count = 0
s = [s[i:i+3] for i in range(0,len(s),3)]
s_new = []
for i in s:
    s_new.append(i[0])
    s_new.append(i[1:3])
if s_new[len(s_new)-1]=='':
    s_new.remove('')
ans = len(s_new)
#print(s_new)
if s_len==2:
    if s_new[0]==s_new[1]:
        print(1)
    else:
        print(ans)
    exit()
for i in range(1,len(s_new),2):
    if i!=len(s_new)-1:
        if s_new[i][0]!=s_new[i][1] and s_new[i][0]!=s_new[i-1] and s_new[i][1]!= s_new[i+1]:
            ans += 1
    else:
        if s_new[i][0]!=s_new[i][1] and s_new[i][0]!=s_new[i-1]:
            ans += 1
print(ans)


### FIXED CODE ###

s = input()
key = s[0]
temp = ''
ans = 1
for i in range(1,len(s)):
    temp += s[i]
    if key != temp:
        ans += 1
        key = temp
        temp = ''


print(ans)
import numpy as np

H,N = map(int,input().split())
INF = 10 ** 10
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(N):
  attack,magic = map(int,input().split())
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    target = j + attack
    if j + attack > H:
      target = H
    if dp[target] > dp[j] + magic:
      dp[target] = dp[j] + magic
      
print(dp[-1])

### FIXED CODE ###

H,N = map(int,input().split())
INF = 10 ** 10
dp = [INF] * (H + 1)
dp[0] = 0

for i in range(N):
  attack,magic = map(int,input().split())
  for j in range(len(dp)):
    if dp[j] == INF:
      continue
    target = j + attack
    if j + attack > H:
      target = H
    if dp[target] > dp[j] + magic:
      dp[target] = dp[j] + magic
      
print(dp[-1])
W,H,N = int(input())
p = 0
q = W
l = 0
m = H

for i in range(N):
  x,y,a = map(int.split())
  if a == 1:
    p = max(p,x)
  if a == 2:
    q = min(q,x)
  if a == 3:
    l = max(l,y)
  if a == 4:
    m = min(m,y)
S = (q-p)*(m-l)
print(S)

### FIXED CODE ###

W,H,N = map(int,input().split())
p = 0
q = W
l = 0
m = H

for i in range(N):
  x,y,a = map(int, input().split())
  if a == 1:
    p = max(p,x)
  if a == 2:
    q = min(q,x)
  if a == 3:
    l = max(l,y)
  if a == 4:
    m = min(m,y)
if (q-p)<0 or (m-l)<0:
  print(0)
  exit()
else:
  S = (q-p)*(m-l)
  print(S)
N,X,M = map(int,input().split())

cnt = [False] + [1] + [0] * (M-1)
numbers = [X]
ans = 0

if M == 0:
  print(0)
  exit()
for n in range(N):
  X = pow((X % M),2)%M
  cnt[X] += 1
  if (cnt[X] >= 2) or X == 0:
    break
  else:
    numbers.append(X) 

if X == 0:
  print(sum(numbers))
  exit()

repeat_before = numbers[0:numbers.index(X)]
repeat = numbers[numbers.index(X):X]

repeat_cnt,mod  = divmod(N-numbers.index(X),len(repeat))


print(sum(repeat_before) + sum(repeat) * repeat_cnt + sum(repeat[:mod]))



### FIXED CODE ###

# 繰り返しの始まり + 繰り返し + 途中で終わった繰り返し分
N,X,M = map(int,input().split())
p = [0] * (M+2)
sum = [0] * (M+2)
p[X] = 1
sum[1] = X

repeat_start = 0
repeat_end = 0

for i in range(2,N+1):
  X = (X**2) % M
  if p[X] != 0:
    repeat_start = p[X]
    repeat_end = i
    break
  else:
    sum[i] = sum[i-1] + X
    p[X] += i

if repeat_start == 0:
  print(sum[N])
else:
  repeat_cnt,mod=divmod(N-repeat_start+1,repeat_end-repeat_start)
  print(repeat_cnt*(sum[repeat_end-1]-sum[repeat_start-1]) + sum[repeat_start+mod-1])
list=[int(input()) for i in range(5)]
sum=sum(list)
max=0
for x in list:
  y = -(-x//10)*10
  max=(y-x, max)
  print(sum-max)

### FIXED CODE ###

X=[int(input()) for i in range(5)]
Y=[]
for x in X:
  Y.append(-(-x//10)*10-x)
print(sum(X)+sum(Y)-(max(Y)))
a,b=map(int,input().split())
if(a+b==15):
      print("+")
elif(a*b=15):
      print("*")
else:
      print("x")
     

### FIXED CODE ###

a,b=map(int,input().split())
if(a+b==15):
      print("+")
elif(a*b==15):
      print("*")
else:
      print("x")
n = int(input())
d = int(input())
ans = n // (2*d + 1)
if n % (2*d + 1) == 0:
  print(ans)
else:
  print(ans+1)


### FIXED CODE ###

r = int(input())

print("{}".format(3*r*r))
N,M = map(int,input().split())
A = list(map(int,input().split()))

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)

k = set(R)
dic = {i:0 for i in k}
for item in R:
  dic[item]+=1

ans = (dic[0]*(dic[0]+1))/2

#for i in k:
 # if i !=0 :
  #  ans += (dic[i]*(dic[i]-1))/2
    

    
print(int(0))


### FIXED CODE ###

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

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)



import collections
c = collections.Counter(R)


ans = 0
for key in c:
  if key == 0:
    ans += (c[key]*(c[key]+1))/2
  else:
    ans += (c[key]*(c[key]-1))/2
  



print(int(ans))
print(input().split()[::-1].join())

### FIXED CODE ###

t=input().split()
print(t[1]+t[0])
N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)


### FIXED CODE ###

N=int(input())
A,X,Y=[],[],[]
for n in range(N):
    An=int(input())
    Xn,Yn=[],[]
    for a in range(An):
        x,y=map(int,input().split())
        Xn.append(x-1)
        Yn.append(y)
    A.append(An)
    X.append(Xn)
    Y.append(Yn)

max_count=0
for k in range(2**N):
    P=[int(_) for _ in bin(k)[2:].zfill(N)]
    ok=True
    for i in range(N):
        for j in range(A[i]):
            if P[i]==1 and P[X[i][j]]!=Y[i][j]:
                ok=False
    if ok:
        max_count=max(max_count,sum(P))
print(max_count)
r = int(input().split())
if r < 1200:
    print('ABC')
elif r < 2800:
    print('ARC')
else:
    print('AGC')

### FIXED CODE ###

r = int(input())
if r < 1200:
    print('ABC')
elif r < 2800:
    print('ARC')
else:
    print('AGC')
N = int(input())
a = [int(input()) for i in range(N)]
n = N
for i in range(N-1):
	j = i + 1
	while j <= N-1:
		if a[i] != a[j]:
			j += 1
		else:
			n -= 2
			break		
print(n)

### FIXED CODE ###

a = int(input())
b = a // 10
c = a % 10

if b == 9 or c == 9 :
	print("Yes")
else :
	print("No")
# -*- coding: utf-8 -*-
from sys import stdin
import math

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N, A, B, K = in_intlist()
NUM = 998244353

def Comb(n, k):
    return math.factorial(n) // (math.factorial(n-k) * math.factorial(k)) 

ans = 0
for i in range(N+1):
    if ((K - i*A) % B == 0) and ((K - i*A) // B <= N):
        ans = (ans + Comb(N, i)*Comb(N, (K - i*A) // B)) % NUM 

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import math

in_strings = lambda: stdin.readline()[:-1] # s = in_strings()
in_int = lambda: int(stdin.readline()) # N = in_int()
in_intlist = lambda: list(map(int, stdin.readline().split())) # List = in_intlist()

N, A, B, K = in_intlist()
NUM = 998244353

# 逆元
Inv = [0 for _ in range(N)]
for i in range(N):
    Inv[i] = pow(i+1, NUM-2, NUM)

# Combination
Comb = [0 for _ in range(N+1)]
Comb[0] = 1
for i in range(1, N+1):
    Comb[i] = (Comb[i-1] * (N-i+1) * Inv[i-1]) % NUM


ans = 0
for i in range(N+1):
    if ((K - i*A) % B == 0) and (0 <= (K - i*A) // B <= N):
        ans = (ans + Comb[i]*Comb[(K - i*A) // B]) % NUM 

print(ans)
def main():
    import fractions
    a, b, c = map(int, input().split())
    a = fractions.sqrt(a)
    b = fractions.sqrt(b)
    c = fractions.sqrt(c)

    if a+b<c:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import math
    a, b, c = map(int, input().split())
    # a = math.sqrt(a)
    # b = math.sqrt(b)
    # c = math.sqrt(c)
    # n = math.sqrt(a*b)

    if 4 * a*b < (c-a-b)**2 and c-a-b > 0:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(100001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())



    gcd =  multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]

    ans = [-1] * (gcd + 1)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != -1 and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()
[N, X, T] = input[] 

a = N/X
b = N//X
k1 = a*T
k2 = k1 + T
if b == 0:
  print(k1)
else:
  print(k2)

### FIXED CODE ###

s = input().split()
N = int(s[0])
X = int(s[1])
T = int(s[2])
a = N//X
b = N%X
k1 = a*T
k2 = k1 + T
if b == 0:
  print(k1)
else:
  print(k2)
import math
S = int(input())
L = 10**9

def search():
    p = int(math.sqrt(S))
    q = p
    i = 0
    while p*q < S:
        if i % 2 == 0 or q == L-1: p += 1
        if i % 2 == 1 or p == L-1: q += 1
        i += 1
    assert p < L and q < L
    target = p*q - S
    divisor = 1
    #assert target < L
    return (0, 0, p, divisor, target, q)

print(*search())

### FIXED CODE ###

import math
S = int(input())
L = 10**9

def search():
    p = int(math.sqrt(S))
    q = p
    i = 0
    while p*q < S:
        if i % 2 == 0 or q == L: p += 1
        if i % 2 == 1 or p == L: q += 1
        i += 1
    assert p <= L and q <= L
    target = p*q - S
    divisor = 1
    #assert target < L
    return (0, 0, p, divisor, target, q)

print(*search())
a,b,c,d=map(int, input().split())
 
while True:
	c=c-b
  	if c<=0:
  		print("Yes")
  		quit()
	a=a-d
  	if a<=0:
  		print("No")
  		quit()

### FIXED CODE ###


a, b, c, d = map( int, input().split() )
#print( a, b, c, d )
 
for i in range( 200 ):
    c = c - b
    if c <= 0:
        print( "Yes" )
        exit()
 
    a = a - d
    if a <= 0:
        print( "No" )
        exit()
def fragOptimalJump(h,n,k):
    dp=[0]*(n+1)
    dp[2]=abs(h[1]-h[2])
    for i in range(3,n+1):
        l=i-k
        if l<0:
            l=1
        min=10000
        for j in range(l,i):
            d=dp[j]+abs(h[i]-h[j])
            if d<min:
                min=d
            
        dp[i]=min
    return dp[n]



N,k=input().split()
N,k=int(N),int(k)
H=[0]*(N+1)
read = [int(n) for n in input().split()]
H=[0]+read
print(H)
print(fragOptimalJump(H,N,k))

### FIXED CODE ###

def fragOptimalJump(h,n):
    dp=[0]*(n+1)
    dp[2]=abs(h[1]-h[2])
    for i in range(3,n+1):
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))
    return dp[n]
  
N=int(input())
read = [int(n) for n in input().split()]
H=[0]+read
print(fragOptimalJump(H,N))
A, B = map(int, raw_input().split())

if (A * B) % 2 == 0:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

A, B = map(int, input().split())
x = A * B
if x % 2 == 0:
    print('No')
else:
    print('Yes')
import math
n,*x=map(int,open(0).read().split())
x.sort()
a=[i-j for i,j in zip(x[1:],x[:-1])]
set(a)
a.sort()
b=[i for i in a if i%a[0]]
b.append(a[0])
if len(b)==1:
    print(*b)
else:
    print(gcd(b[0],b[1]))    

### FIXED CODE ###

import fractions
n,*x=map(int,open(0).read().split())
x.sort()
a=[i-j for i,j in zip(x[1:],x[:-1])]
set(a)
a.sort()
b=[i for i in a if i%a[0]]
b.append(a[0])
if len(b)==1:
    print(*b)
else:
    ans=b[0]
    for i in b[1:]:
        ans=fractions.gcd(ans,i)
    print(ans)
import numpypy as np

### FIXED CODE ###

AB, BC, CA = map(int, input().split())

result = int(AB * BC / 2)

print(result)
s = input()
if s = AAA and s = BBB :
    print('No')
else:
    print('Yes')

### FIXED CODE ###

s = input()
if (s[0] != s[1] or s[0] != s[2]):
    print('Yes')
else:
    print('No')
N = int(input())
list = list(map(int, input().split()))
no = 0 
ans = 1
lens = 0
if list.count("0") >0:
  print("0")
  exit()
else:
  for i in range(N):
    ans = ans * list[no]
    lens = lens + len(list[no])
    no += 1
    if lens >= 19:
      exit()
    else:
      continue
print(ans)

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    if 0 in A:
        print(0)
        exit()
    for i in A:
        ans *= i
        if ans > 10**18:
            print(-1)
            exit()
    print(ans)
resolve()
def main():
    S = input()
    cnt = 0
    for i in range(4):
        if s[i]=='o':
            cnt += 1
    ans = 700 + cnt * 100
    print(ans)
main()

### FIXED CODE ###

def main():
    S = input()
    cnt = 0
    for i in range(3):
        if S[i]=='o':
            cnt += 1
    ans = 700 + cnt * 100
    print(ans)
main()
def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


N = int(input())
X = input()
cnt = X.count("1")

if cnt == 0:
    for _ in range(N):
        print(1)
    exit()
if cnt == 1:
    if X[-1] == "0":
        res = 0
    else:
        res = 1
    for i, x in enumerate(X):
        if x == "1":
            print(0)
        else:
            print(res)
    exit()


res = [0]*21
for i in range(1, 19):
    tmp = 0
    x = i
    while x:
        cnt = pop_count(x)
        x %= cnt
        tmp += 1
    res[i] = tmp


cnt = X.count("1")
Xrev = X[::-1]
sum01 = 0
sum10 = 0
memo01 = [0] * N
memo10 = [0] * N

for i, x in enumerate(Xrev):
    val01 = pow(2, i, cnt + 1)
    val10 = pow(2, i, cnt - 1)
    if x == "1":
        sum01 += val01
        sum01 %= cnt + 1
        sum10 += val10
        sum10 %= cnt - 1
    memo01[i] = val01
    memo10[i] = val10
memo01.reverse()
memo10.reverse()

for i, x in enumerate(X):
    if x == "0":
        p = (sum01 + memo01[i]) % (cnt + 1)
        print(1 + res[p])
    else:
        p = (sum10 - memo10[i] + cnt - 1) % (cnt - 1)
        print(1 + res[p])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
X = input()
pc = X.count("1")

if pc == 1:
    if X[-1] == "0":
        for i, s in enumerate(X):
            if i == N - 1:
                print(2)
            elif s == "0":
                print(1)
            else:
                print(0)
    else:
        ans = [2] * (N - 1) + [0]
        print(*ans, sep="\n")
    exit()


m01 = 0
m10 = 0
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "1":
        m01 += b01
        m01 %= pc + 1
        m10 += b10
        m10 %= pc - 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1


def pop_count(T):
    T = (T & 0x55555555) + ((T >> 1) & 0x55555555)
    T = (T & 0x33333333) + ((T >> 2) & 0x33333333)
    T = (T & 0x0F0F0F0F) + ((T >> 4) & 0x0F0F0F0F)
    T = (T & 0x00FF00FF) + ((T >> 8) & 0x00FF00FF)
    T = (T & 0x0000FFFF) + ((T >> 16) & 0x0000FFFF)
    return T


memo = [0] * (N + 10)
for i in range(1, N + 10):
    p = pop_count(i)
    memo[i] = memo[i % p] + 1


ans = [0] * N
b01 = 1
b10 = 1
for i, s in enumerate(X[::-1]):
    if s == "0":
        m = m01
        m += b01
        m %= pc + 1
    else:
        m = m10
        m -= b10
        m %= pc - 1
    ans[i] = memo[m] + 1
    b01 *= 2
    b01 %= pc + 1
    b10 *= 2
    b10 %= pc - 1

print(*ans[::-1], sep="\n")
import math
debt = 100000
n = int(raw_inpu())
for i in range(n):
    debt = math.ceil(debt*1.05,3)
print debt

### FIXED CODE ###

import math
debt = 100000
n = int(raw_input())
for i in range(n):
    debt = int(math.ceil(debt*1.05/1000)*1000)
print debt
L,R=map(int,input().split(' '))
l,r=L%2019,R%2019
D=R-L
d=r-l
if D<2019:
  if D==d:
    if 
    print( (l*(l+1))%2019 )
  else:
    print(0)
else:
  print(0)

### FIXED CODE ###

import numpy as np
L,R=map(int,input().split(' '))
l,r=L%2019,R%2019
D=R-L
d=r-l
if D<2019:
  if D==d:
    res=[]
    for i in range(L,R+1):
      for j in range(i+1,R+1):
        res.append((i*j)%2019)
    print(min(res))
  else:
    print(0)
else:
  print(0)
N, Y = map(int, input().split())
Y = Y / 1000

isTrue = False
for i in range(N+1):
    for j in range(N-i+1):
        for k in range(N-i-j+1):
            if 10*i + 5*j + k == Y:
                isTrue = True
                print("{} {} {}".format(i, j, k))
                break
        else:
            continue
        break
    else:
        continue
    break

if not isTrue:
    print("-1 -1 -1")

### FIXED CODE ###

print("2018"+input()[4:])