Harryxun/stf_run huggingface dataset:
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # G 点に満たなければ nokori のうち一番大きいものを解く
        if sum < g:
            use = max(nokori)
            # 解く問題が問題数を超えないように注意
            n = min(-(-(g - sum) // (use * 100)))
            count += n
            sum += n * use * 100

        if sum >= g:
            ans = min(ans, count) 
    else:
        # 総合スコア、解いた問題数、まだ解いてない問題を更新
        dfs(i + 1, sum, count, nokori)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100\
        + pc[i][1], count + pc[i][0], nokori - {i + 1})


d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

dfs(0, 0, 0, set(range(1, d + 1)))
print(ans)

### FIXED CODE ###

# まだ解いてない配点を nokori として持つ
def dfs(i, sum, count, nokori):
    global ans
    if i == d:
        # G 点に満たなければ nokori のうち一番大きいものを解く
        if sum < g:
            use = max(nokori)
            # 解く問題が問題数を超えないように注意
            n = min(pc[use - 1][0], -(-(g - sum) // (use * 100)))
            count += n
            sum += n * use * 100

        if sum >= g:
            ans = min(ans, count)
    else:
        # 総合スコア、解いた問題数、まだ解いてない問題を更新
        dfs(i + 1, sum, count, nokori)
        dfs(i + 1, sum + pc[i][0] * (i + 1) * 100 + pc[i][1], count + pc[i][0], nokori - {i + 1})


d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

ans = float("inf")

dfs(0, 0, 0, set(range(1, d + 1)))
print(ans)
import math
n, m = map(int, input().split())
MOD = 1000000007
a, b = n, m
count_n = n
count_m =m
count = 0
if abs(n-m) == 1:
  count_n = math.factorial(n) / MOD
  count_m = math.factorial(m) / MOD
  count = count_m * count_n % MOD
elif abs(n-m) == 0:
  count_n = math.factorial(n) % MOD
  count_m = math.factorial(m) % MOD
  count = 2 * count_m * count_n % MOD
else:
  count = 0

print(count % MOD)

### FIXED CODE ###

import math
n, m = map(int, input().split())
MOD = 1000000007
count_n = 0
count_m = 0
count = 0
if abs(n-m) == 1:
  count_n = math.factorial(n) % MOD
  count_m = math.factorial(m) % MOD
  count = count_m * count_n % MOD
elif abs(n-m) == 0:
  count_n = math.factorial(n) % MOD
  count_m = math.factorial(m) % MOD
  count = 2 * count_m * count_n % MOD
else:
  count = 0

print(count % MOD)
s = input()
t = input()
l = []
for i in range(len(t)):
    for j in range(i+1,len(t)+1):
        if t[i:j] in s[i:]:
            l.append(t[i:j])
l2 = []
for j in l:
    l2.append(len(j))
            
print(len(t) - max(l2))

### FIXED CODE ###

s = input()
t = input()
l = []
for i in range(len(s)-len(t)+1):
    s2 = s[i:]
    cnt = 0
    for j in range(len(t)):
        if s2[j] == t[j]:
            cnt += 1
    l.append(cnt)
print(len(t)-max(l))
comb_memo = {}
def comb(n, r):
  global comb_memo
  if (n, r) in comb_memo:
    return comb_memo[(n, r)]
  else:
    r = min(r, n-r)
    res = 1
    for _ in range(r):
      res *= n
      n -= 1
    for i in range(1, r+1):
      res //= i
    comb_memo[(n, r)] = res
    comb_memo[(n, n-r)] = res
    return res

N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)

mu = sum(v[:A]) / A
if v[0] == mu:
  R = v.count(v[0])

ans = 0
if R > A:
  for i in range(A, B+1):
    if i > R:
      break
    ans += comb(R, i)
else:
  min_v = v[A-1]
  n = v.count(min_v)
  need = v[:A].count(min_v)
  ans += comb(n, need)

print(mu)
print(ans)

### FIXED CODE ###

comb_memo = {}
def comb(n, r):
  global comb_memo
  if (n, r) in comb_memo:
    return comb_memo[(n, r)]
  else:
    r = min(r, n-r)
    res = 1
    for _ in range(r):
      res *= n
      n -= 1
    for i in range(1, r+1):
      res //= i
    comb_memo[(n, r)] = res
    comb_memo[(n, n-r)] = res
    return res

N, A, B = map(int, input().split())
v = list(map(int, input().split()))
v.sort(reverse=True)

mu = sum(v[:A]) / A
ans = 0
if v[0] == mu:
  R = v.count(v[0])
  for i in range(A, B+1):
    if i > R:
      break
    ans += comb(R, i)
else:
  min_v = v[A-1]
  n = v.count(min_v)
  need = v[:A].count(min_v)
  ans += comb(n, need)

print(mu)
print(ans)
# -*- coding: utf-8 -*-
"""
Created on Sat Sep 23 19:10:57 2017

@author: taichiNakamura
"""

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
# スペース区切りの整数の入力
a = map(int, input().split())

favorite = 0
for i,ai in enumerate(a):
    if a[ai-1] == (i+1):
        favorite += 1

print(favorite//2)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Sep 23 19:10:57 2017

@author: taichiNakamura
"""

# -*- coding: utf-8 -*-
# 整数の入力
N = int(input())
# スペース区切りの整数の入力
a = input().split()

a = list(map(int, a))

favorite = 0
for i,ai in enumerate(a):
    if a[ai-1] == (i+1):
        favorite += 1

print(favorite//2)
s=str(input())
if s.isupper()=True:
  print("A")
else:
  print("a")

### FIXED CODE ###

s=str(input())
if s.isupper()==True:
  print("A")
else:
  print("a")
import numpy as np


def read():
    H, N = list(map(int, input().strip().split()))
    A = list()
    B = list()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return H, N, A, B


def solve(H, N, A, B, INF=10**9):
    BMAX = max(B)
    dp = np.empty(H + BMAX + 1, dtype=np.int32)
    dp[:] = INF
    dp[0] = 0
    for h in range(0, H + BMAX + 1, A[0]):
        dp[h] = dp[h-A[0]] + b[0]
    
    for h in range(0, H + BMAX + 1):
        for i in range(N):
            if h - A[i] >= 0:
                dp[h] = min(dp[h], dp[h - A[i] + B[i])
    return dp[H]


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

from collections import deque


def read():
    H, N = list(map(int, input().strip().split()))
    A = list()
    B = list()
    for i in range(N):
        a, b = list(map(int, input().strip().split()))
        A.append(a)
        B.append(b)
    return H, N, A, B


def solve(H, N, A, B, INF=10**9):
    BMAX = max(B)
    dp = [[INF for i in range(N)] for h in range(H + BMAX + 1)]
    for i in range(0, N):
        dp[0][i] = 0
    for h in range(0, H + BMAX + 1):
        for i in range(N):
            if i == 0:
                if h - A[i] >= 0:
                    dp[h][i] = dp[h - A[i]][i] + B[i]
            else:
                if h - A[i] >= 0:
                    dp[h][i] = min(dp[h][i-1], dp[h - A[i]][i] + B[i])
                else:
                    dp[h][i] = dp[h][i-1]
    min_b = INF
    for h in range(H, H + BMAX + 1):
        for i in range(N):
            min_b = min(min_b, dp[h][i])
    return min_b


if __name__ == "__main__":
    inputs = read()
    print("%s" % solve(*inputs))
a, b = map(int, raw_input().split())
print(a * b, 2 * (a + b))



### FIXED CODE ###

a, b = list(map(int, input().split()))
print(a * b, 2 * (a + b))
def main():
    import sys
    input = sys.stdin.readline

    INF = 1 << 30

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

    dp = [INF] * (H * 2 + 1)
    dp[0] = 0

    for _ in range(N):
        A, B = map(int, input().split())
        for j in range(H):
            dp[j + A] = min(dp[j + A], dp[j] + B)
    print(min(dp[H:]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys

    input = sys.stdin.readline

    inf = 10 ** 8 + 10

    h, n = map(int, input().split())
    *ab, = (list(map(int, input().split())) for _ in range(n))

    dp = [[inf] * (h + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    # dp[使った魔法][与えたダメージ]=最小魔法消費

    for i, (a, b) in enumerate(ab):
        for hp in range(h + 1):
            if hp < a:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][0] + b)
            else:
                dp[i + 1][hp] = min(dp[i][hp], dp[i + 1][hp - a] + b)

    print(dp[n][h])


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
for i in range(n): #aは偶数なので、1/2した値の配列を作った
    b.append(int(a[i]/2))

def lcm(x,y): #最小公倍数を求める関数の定義
    return (x*y)//fractions.gcd(x,y)

c=[lcm(b[0],b[1])] #以下のサイクルで求めた最小公倍数を入れる配列
for i in range(1,n):
    x=lcm(c[i-1],b[i])
    c.append(x)
    if x<m:
        continue
    else:
        break

d=int(m//c[len(c)-1]) #最後の値(c[len(c)-1])が配列bの最小公倍数
ans=int((d+1)//2)
print(ans)

### FIXED CODE ###

import math
import fractions
n,m=map(int, input().split())
a=list(map(int, input().split()))
b=[]
s=math.floor(math.log2(max(a)))
buf=0
for i in range(n): #aは偶数なので、1/2した値の配列を作った
    b.append(int(a[i]//2))

for i in range(s+1): #2のi乗ですべての数が割れるかどうか
    for j in b:
        if j%(2**i)==0:
            buf+=1
        else:
            continue
    if buf==n:
        buf=0
        continue
    else:
        break

def lcm(x,y): #最小公倍数を求める関数の定義
    return (x*y)//fractions.gcd(x,y)

if buf!=0 and buf!=n: #偶奇が入り混じってるとき
    print(0)
elif n==1: #配列の要素が1つしかないとき
    d=int(m//b[0])
    print(int((d+1)//2))
else:
    c=[lcm(b[0],b[1])] #以下のサイクルで求めた最小公倍数を入れる配列
    for i in range(1,n):
        x=lcm(c[i-1],b[i])
        c.append(x)
        if x<m:
            continue
        else:
            break
    d=int(m//c[len(c)-1]) #最後の値(c[len(c)-1])が配列bの最小公倍数
    ans=int((d+1)//2)
    print(ans)
class segtree:
    def __init__(self, nn):
        self.NN = nn
        self.XX = [0] * (2**(nn+1)-1)
    def getmax(self, i):
        j = 2**self.NN + i - 1
        ma = -1
        while j >= 0:
            ma = max(ma, self.XX[j])
            j = (j-1) // 2
        return -1 if ma <= 0 else INF - ma
    def updaterange(self, a, b, x):
        l = a + (1<<self.NN)
        r = b + (1<<self.NN)
        s = 0
        while l < r:
            if l%2:
                self.XX[l-1] = max(self.XX[l-1], x)
                l += 1
            if r%2:
                r -= 1
                self.XX[r-1] = max(self.XX[r-1], x)
            l >>= 1
            r >>= 1

N, Q = map(int, input().split())
st = segtree(17)
INF = 1<<50
for _ in range(N):
    s, t, x = map(int, input().split())
    st.updaterange(s-x, t-x, INF-x)
for _ in range(Q):
    print(st.getmax(int(input())))

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left as bl
class segtree:
    def __init__(self, nn):
        self.NN = nn
        self.XX = [0] * (2**(nn+1)-1)
    def getmax(self, i):
        j = 2**self.NN + i - 1
        ma = -1
        while j >= 0:
            ma = max(ma, self.XX[j])
            j = (j-1) // 2
        return -1 if ma <= 0 else INF - ma
    def updaterange(self, a, b, x):
        l = a + (1<<self.NN)
        r = b + (1<<self.NN)
        s = 0
        while l < r:
            if l%2:
                self.XX[l-1] = max(self.XX[l-1], x)
                l += 1
            if r%2:
                r -= 1
                self.XX[r-1] = max(self.XX[r-1], x)
            l >>= 1
            r >>= 1

N, Q = map(int, input().split())
st = segtree(18)
INF = 1<<50
X = []
D = []
for _ in range(N):
    s, t, x = map(int, input().split())
    X.append((s, t, x))
for _ in range(Q):
    D.append(int(input()))

for s, t, x in X:
    st.updaterange(bl(D, s-x), bl(D, t-x), INF-x)
for i in range(Q):
    print(st.getmax(i))
n = list(map(int,input().split()))
print(n[1] n[2] n[3])

### FIXED CODE ###

n = list(map(int,input().split()))
print(n[2],n[0],n[1])
x,y=input().split(" ")
z=x*y
o=(x+y)*2
print(z o)

### FIXED CODE ###

x = map(int,raw_input().split())
z=x[0]*x[1]
a=(x[0]+x[1])*2
print z,a
inport sys

x = sys.stdin.readline()

a, b = x.split(" ")

a = int(a)
b = int(b)

S = a * b
l = 2 * (a + b)

print '%d %d' % (S,l)

### FIXED CODE ###

import sys

x = sys.stdin.readline()

a, b = x.split(" ")

a = int(a)
b = int(b)

S = a * b
l = 2 * (a + b)

print '%d %d' % (S,l)
N=int(input())
sum=0
for i range(N):
  l, r =map(int, input().split())
  sum+=(r-l+1)
print(100000-sum)

### FIXED CODE ###

n=int(input())
sum=0
for i in range(n):
  l, r =map(int, input().split())
  sum+=(r-l+1)
print(sum)
n = int(input())
ls = [int(i) for i in input().split()]


from collections import defaultdict
d1 = defaultdict(int)
d2 = defaultdict(int)

for i in range(n):
    if i%2==0:
        d1[ls[i]]+=1
    else:
        d2[ls[i]]+=1


d1=sorted(d1.items())
d2=sorted(d2.items())


if d1[0][0] != d2[0][0]:
    print(n-d1[0][1]-d2[0][1])
else:
    if len(d1)==1 and len(d2)==2:
        print(min(n-d1[0][1]-d2[1][1],n-d2[0][1]))
    elif len(d1)==2 and len(d2)==1:
        print(min(n-d1[1][1]-d2[0][1],n-d1[0][1]))
    else:
        print(min(n-d1[1][1]-d2[0][1],n-d1[0][1]-d2[1][1]))


### FIXED CODE ###

n = int(input())
ls = [int(i) for i in input().split()]


from collections import defaultdict
d1 = defaultdict(int)
d2 = defaultdict(int)

for i in range(n):
    if i%2==0:
        d1[ls[i]]+=1
    else:
        d2[ls[i]]+=1


d1=sorted(d1.items(),key=lambda x:x[1],reverse=True)
d2=sorted(d2.items(),key=lambda x:x[1],reverse=True)


if d1[0][0] != d2[0][0]:
    print(n-d1[0][1]-d2[0][1])
else:
    if len(d1)==1 and len(d2)==1:
        print(min(n-d1[0][1],n-d2[0][1]))
    elif len(d1)==1 and len(d2)==2:
        print(min(n-d1[0][1]-d2[1][1],n-d2[0][1]))
    elif len(d1)==2 and len(d2)==1:
        print(min(n-d1[1][1]-d2[0][1],n-d1[0][1]))
    else:
        print(min(n-d1[1][1]-d2[0][1],n-d1[0][1]-d2[1][1]))
import sys
A = list(map(int, input().split()))
N = int(input())

if len(A) == len(set(A)):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
if len(A) == len(set(A)):
    print("YES")
else:
    print("NO")
#inp = list(map(int, input().split()))
S = input()
T = input()

tmp = []*len(T)

i=0
while i < len(T):
  for j in range(i, len(T)-i):
    if T[i:i+j+1] in S:
      tmp[i] = j
  i = tmp[i]
      
print(max(tmp))

### FIXED CODE ###

S=input()
T=input()
ls=len(S)
lt=len(T)
ans=lt
for i in range(0,ls-lt+1):
    a=0
    for j in range(lt):
        if S[i+j]==T[j]:
            a+=1
    ans=min(ans,lt-a)
print(ans)
N,K=map(int,input().split())
d={}
l=map(int,input().split())
for i in l:
  if not i in d:
    d[i]=1
  else:
    d[i]+=1
c=0
e=list(sorted(d.items(),key=lambda x:x[1]))[len(d)-K:]
for i in e:
  c+=e[1]

### FIXED CODE ###

N,K=map(int,raw_input().split())
d={}
l=map(int,raw_input().split())
for i in l:
  if not i in d:
    d[i]=1
  else:
    d[i]+=1
c=0
e=sorted(d.items(),key=lambda x:x[1])[:len(d.items())-K]
for i in e:
  c+=i[1]
print(c)
strstart = input()
wzc = 0
wzf = 0
for i in strstart:
    i2 += 1
    if i == 'c':
        wzc = i2
    if i == 'F':
        wzf = i2
        break
if wzc < wzf:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

s=input();pd=0
for i in range(0,len(s)):
    if s[i]=='C':
        pd=1
    if s[i]=='F'and pd==1:
        print('Yes')
        pd=2
        break
if pd!=2:
    print('No')
n = int(input())
output = []
arr = list(map(int, input().split()))
k = int(input())
for _ in range(k):
  a,b = map(int, input().split())
  arr[arr.index(a)] = b
  output.append(sum(arr))
for i in output:
  print(i)

### FIXED CODE ###

n = int(input())
arr = list(map(int, input().split()))
k = int(input())
s = sum(arr)
d = {}
for i in arr:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
for _ in range(k):
    v = 0
    a,b = map(int, input().split())
    if a not in d:
        print(s)
        continue
    s += (b-a) * d[a]
    if b in d:
        d[b] += d[a]
    else:
        d[b] = d[a]
    print(s)
    del d[a]
import math
n=int(input())
dp=[math.inf]*(n+1)
dp[0]=0
for i in range(n):
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=6
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=9
print(dp[n])

### FIXED CODE ###

n=int(input())
dp=[float("inf") for _ in range(n+1)]
dp[0]=0
for i in range(n):
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=6
    power=1
    while i+power <= n:
        dp[i+power] = min(dp[i+power],dp[i]+1)
        power*=9
print(dp[n])
import itertools

A=[]
for i in range(3):
    try:
        A.append(list(map(int,input().split())))
    except:
        break;
A = list(itertools.chain.from_iterable(A))
n = int(input())
b=[int(input()) for i in range(n)]

for i in b:
    if i in A:
        
#print(A)
#print(b)

### FIXED CODE ###

a=[]
for i in range(3):
  a.append(list(map(int,input().split())))
n = int(input())
x = 0

for i in range(n):
  b = int(input())
  for j in range(3):
    for k in range(3):
      if a[j][k] == b:
        a[j][k] = 0

if (a[0][0] == 0 and a[2][2] == 0 and a[1][1] == 0) or (a[0][2] == 0 and a[2][0] == 0 and a[1][1] == 0): #斜めに揃っていたら
  print("Yes")
  x = 1
for i in range(3):
  if a[i][0] == 0 and a[i][1] == 0 and a[i][2] == 0 and x == 0: #横に揃っていたら
    print("Yes")
    x = 1
    break
  elif a[0][i] == 0 and a[1][i] == 0 and a[2][i] == 0 and x == 0: #縦に揃っていたら
    print("Yes")
    x = 1
    break
if x == 0:
  print("No")
import sys
import math


def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


fin = sys.stdin.readline
N, K = [int(elem) for elem in fin().split()]

for i in range(1, K):
    if (N-K+1) < i:
        print(0)
    else:
        result = int(permutations_count(N-K+1, i) / math.factorial(i-1))
        print(int(result % 1000000007))

if (N-K+1) < K:
    print(0)
else:
    result = int(combinations_count(N-K+1, K))
    print(int(result % 1000000007))


### FIXED CODE ###

import sys
import math


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


fin = sys.stdin.readline
N, K = [int(elem) for elem in fin().split()]

for i in range(1, K+1):
    if (N-K+1) < i:
        print(0)
    else:
        result = int(combinations_count(N-K+1, i) * combinations_count(K-1, i-1))
        print(int(result % 1000000007))
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
from heapq import *
import json
l=[]
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
l.sort(key=lambda x:x[0],reverse=True)
ans=0
num=N-1
for i in range(len(l)):
    if i==0:
        ans=ans+l[i][0]*min(2*l[i][1]-1,num)
        num=num-min(2*l[i][1]-1,num)
    else:
        ans=ans+l[i][0]*min(2*l[i][1],num)
        num=num-xmin(2*l[i][1],num)
print(ans)

### FIXED CODE ###

from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
from heapq import *
import json
l=[]
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
values=list(c.values())	#aのCollectionのvalue値のリスト(n_1こ、n_2こ…)
key=list(c.keys())	#先のvalue値に相当する要素のリスト(要素1,要素2,…)
for i in range(len(key)):
    l.append([key[i],values[i]])#lは[要素i,n_i]の情報を詰めたmatrix
l.sort(key=lambda x:x[0],reverse=True)
ans=0
num=N-1
for i in range(len(l)):
    if i==0:
        ans=ans+l[i][0]*min(2*l[i][1]-1,num)
        num=num-min(2*l[i][1]-1,num)
    else:
        ans=ans+l[i][0]*min(2*l[i][1],num)
        num=num-min(2*l[i][1],num)
print(ans)
2
6 8
3 3

### FIXED CODE ###


n = int(input())
ans = 0

for i in range(n):
    l,r = map(int,input().split())
    ans += r-l+1

print(ans)
a,b=map(int,input().split());print("{:d},{:d},{:.10f}".format(a//d,a%b,a/b))


### FIXED CODE ###

a,b=map(int,input().split());print(a//b,a%b,"{:.10f}".format(a/b))
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N = S()
    N =  N[::-1]
    cnt = 0
    next = 0
    for i in range(len(N)):
        num = int(N[i])
        num += next
        if num <= 4:
            cnt += num
            next = 0
        elif num >= 6:
            cnt += 10 - num
            next = 1
        else:
            if int(N[i + 1]) <= 4:
                cnt += num
                next = 0
            else:
                cnt += 10 - num
                next = 1

    if next == 1:
        cnt += 1
    print(cnt)
if __name__ == "__main__":
    main()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

from collections import deque
from collections import defaultdict
def main():
    N = S()
    N =  N[::-1]
    N += '0'
    cnt = 0
    next = 0
    for i in range(len(N)):
        num = int(N[i])
        num += next
        if num <= 4:
            cnt += num
            next = 0
        elif num >= 6:
            cnt += 10 - num
            next = 1
        else:
            if int(N[i + 1]) <= 4:
                cnt += num
                next = 0
            else:
                cnt += 10 - num
                next = 1

    print(cnt)
if __name__ == "__main__":
    main()
import numpy as np
def kouho(x, y, h):
    if h:
        return np.abs(np.arange(101) - x)[:, np.newaxis]  + np.abs(np.arange(101) - y) [np.newaxis] + h

n = int(input())
arrs = []
for _ in range(n):
    arrs.append(kouho(*(map(int, input().split()))))
arrs = np.array(arrs)
v = arrs.var(0)
m = arrs.mean(0)
for i in range(101):
  for j in range(101):
    if v[i, j]==0:
      print(i, j, int(m[i, j]))
      break

### FIXED CODE ###

def ni(): 
    return int(input())
def li():
    return map(int, input().split())

xyh = [tuple(li()) for _ in range(ni())]
xmax, ymax, hmax = max(xyh, key=lambda _: _[-1])

for x_cent in range(101):
    for y_cent in range(101):
        h_cent = hmax + abs(xmax-x_cent) + abs(ymax-y_cent)
        
        for x, y, h in xyh:
            if h != max(0, h_cent - abs(x-x_cent) - abs(y-y_cent)):
                break
        else:
            print(x_cent, y_cent, h_cent)
n=int(input())

s=input()
x=int(s,2)
ans=[]

ans_memo=[0]*(2**(n+1))
#ans_memo[1]=1
#ans_memo[2]=1

def DEF(x,cnt):
    global ans_memo
    #print(x,cnt,ans_memo)
    if ans_memo[x]!=0:
        return ans_memo[x]
    else:
        if x%(str(bin(x)).count("1"))==0:
            ans_memo[x]=1
            return 1
        else:
            tmp=DEF(x%(str(bin(x)).count("1")),cnt+1)+1
            ans_memo[x]=tmp
            return tmp

ans=[]

for i in range(n):
    tmp=2**(n-i-1)
    tmp_num=x

    #1の時
    if tmp&tmp_num:
        tmp_num-=tmp
        ans.append(DEF(tmp_num,0))
        
    else:
        tmp_num+=tmp
        ans.append(DEF(tmp_num,0))

#print(ans_memo)

for item in ans:
    print(item)
            









### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

n=int(input())
s=input()
X=int(s,2)

one_cnt=popcount(X)

modp=X%(one_cnt+1)
modm=X%(one_cnt-1) if one_cnt-1!=0 else 0

for i in range(n):
    if s[i]=="1":
        if one_cnt-1==0:
            print(0)
            continue
        else:
            num=(modm-pow(2,n-i-1,one_cnt-1))%(one_cnt-1)
    else:
        num=(modp+pow(2,n-i-1,one_cnt+1))%(one_cnt+1)

    #print(i,"num",num)
    cnt=1
    while num!=0:
        num=num%popcount(num)
        cnt+=1
    print(cnt)