Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
# input
from collections import deque
import itertools

n, m = map(int, input().split())
a, b = [0] * (n), [0] * (n)
path = [[] for _ in range(n)]
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1
    b[i] -= 1
    path[a[i]].append(b[i])
    path[b[i]].append(a[i])
# n-1 ! を全探索する
all_lis = itertools.permutations(range(1, n))  # 1(0)は出発点なので除く
# print(all_lis)

ans = 0
for i in all_lis:
    start = 0
    ok = 1
    for j in range(n - 1):
        if i[j] not in path[start]:
            ok = 0
            break
        else:
            start = i[j]
    if ok:
        ans += 1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
# input
from collections import deque
import itertools

n, m = map(int, input().split())
path = [[] for _ in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    path[a].append(b)
    path[b].append(a)
# n-1 ! を全探索する
all_lis = itertools.permutations(range(1, n))  # 1(0)は出発点なので除く
# print(all_lis)

ans = 0
for i in all_lis:
    start = 0# これをfor の外においていて爆死。
    ok = 1
    for j in range(n - 1):
        if i[j] not in path[start]:
            ok = 0
            break
        else:
            start = i[j]
    if ok:
        ans += 1
print(ans)
import math
from functools import reduce
import numpy as np


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n=int(input())
a=np.array([int(i) for i in input().split()])

if n==2:print(max(a))
else:
    ans=0
    for i in range(n):
        b=np.array([x for x in a if not x==a[i]])
        c=gcd_list(b)
        if ans<c: ans=c
    print(ans)
    

### FIXED CODE ###

#c
n=int(input())
a=[int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
l=[1]*n
r=[1]*n
l[0]=a[0]
r[0]=a[n-1]
for i in range(1,n):
    l[i] = gcd(l[i-1],a[i])
    r[i] = gcd(r[i-1],a[n-i-1])
if n>=3:
    ans = max(l[-2],r[-2],max(gcd(l[i-1],r[n-i-2]) for i in range(1,n-1)))
    print(ans)
else:
    print(max(a))
while True:
  a,op,c = map(str, input().split())
  a = int(a)
  c = int(c)
  if op == '?': 
    break
  if op == '+':
    print(a+b)
  if op == '-':
    print(a-b)
  if op == '*':
    print(a*b)
  if op == '/':
    print(a//b)


### FIXED CODE ###

while True:
  a,op,b = map(str, input().split())
  a = int(a)
  b = int(b)
  if op == '?': 
    break
  if op == '+':
    print(a+b)
  if op == '-':
    print(a-b)
  if op == '*':
    print(a*b)
  if op == '/':
    print(a//b)
s=input()
if s =='ABC' :print('ARC')
else if s=='ARC':print('ABC')


### FIXED CODE ###

s=input()
if s =='ABC' :print('ARC')
elif s=='ARC':print('ABC')
from scipy.special import comb

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

p = 10 ** 9 + 7

print((2 ** n - comb(n, a, exact=True) - comb(n, b, exact=True)) % p - 1)

### FIXED CODE ###

k = 2 *10**5
mod = 10**9+7

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

modinv_table = [-1]*(k+1)
for i in range(1,k+1):
    modinv_table[i] = pow(i,-1,mod)

def binomial_coefficients(n,k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i+1]
        ans %= mod
    return ans
print((pow(2,n,mod)-binomial_coefficients(n,a)-binomial_coefficients(n,b)-1)%mod)
a,b = (int(x) for x in input().split(" "))
int(c) = (int(a) - int(b))
if c > ('-1'):
    print int(c)
elif int(c) < ('0'):
    print('0')

### FIXED CODE ###

X, t = map(int, input().split())
x = X - t
 
if x > 0:
    print(x)
else:
    print(0)
n = int(input())
X = list(map(int, input().split()))
x_min = min(X)
x_max = max(X)

min_val = 10**6 + 1

for i in range(x_min, x_max + 1):
    min_val = min(min_val, sum(map(lambda x: (x-i)**2, X)))

print(min_val)

### FIXED CODE ###

N, R = list(map(int, input().split()))
print(R if N >= 10 else R + 100*(10-N))
i = 0

while True:
 n = int(input())
  if n == 0:break

   print("Case {}: {}".format(i, n))

   i += 1

### FIXED CODE ###

i = 0

while True:
 n = int(input())
 i += 1
 if n == 0:
  break
 print("Case {}: {}".format(i, n))
s = input()
s = s.split(" ")
a = int(s[0])
b = int(s[1])
c = int(s[2])
res = b // x
res -= ((a - 1) // x)
print(res)

### FIXED CODE ###

s = input()
s = s.split(" ")
a = int(s[0])
b = int(s[1])
x = int(s[2])
res = b // x
res -= ((a - 1) // x)
print(res)
A, B = map(int, input().split())

print(int(A*B))

### FIXED CODE ###

from decimal import *
getcontext().prec = 18

a, b = input().split()
ans = int(a) * Decimal(b)
print(int(str(ans)[:-3]))
import fractions
def two_avvreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


N, M = [int(a) for a in input().split()]
S = int(input())
T = int(input())

print(str(two_avvreviation(N, M, S, T)))

### FIXED CODE ###

import fractions


def two_abbreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


N, M = [int(a) for a in input().split()]
S = str(input())
T = str(input())

print(str(two_abbreviation(N, M, S, T)))
n = int(input())
a = map(int,input().Split(' '))
count = 0;
while true:
	for i in a :
  		if i%2!=0:
          break
        else :
          a[i] = a%i
    count++
    
print(str(count))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split(' ')))
count = 0;
flag =True
while True:
    for i in a :
        if i % 2 != 0 :
            flag=False
            break
    if flag :
        a = list(map(lambda x: x/2 , a))
        count=count+1
    else:
        break
    
print(str(count))
i = input().split()

a = i[0]
b = i[1]
c = i[2]
d = i[3]

if int(d) <= int(a):
  print(int(d))
  elif int(d) - int(a) <= int(b):
    print(int(a))
else:
  print(int(a) - (int(d) - int(a) -int(b)))

### FIXED CODE ###

i = input().split()

a = i[0]
b = i[1]
c = i[2]
d = i[3]

if int(d) <= int(a):
  print(int(d))
elif int(d) - int(a) <= int(b):
    print(int(a))
else:
  print(int(a) - (int(d) - int(a) -int(b)))
import math

n=int(input())
a_array=list(map(int,input().split()))
next_xor=[0 for _ in range(n-1)]
max_dig=math.floor(math.log2(a_array[0]))
for i in range(n-1):
    next_xor[i]=a_array[i]^a_array[i+1]
    max_dig=math.floor(math.log2(a_array[i+1]))
flag_1=True
ans_1=[0]
ans_2=[2<<max_dig]
SUP=10**9
for xo in next_xor:
    if ans_1[-1]^xo >= SUP:
        flag_1=False
    ans_1.append(ans_1[-1]^xo)
    ans_2.append(ans_2[-1]^xo)
print(" ".join(map(str,ans_1 if flag_1 else ans_2)))

### FIXED CODE ###

n=int(input())
a_array=list(map(int,input().split()))
all_xor=0
for a in a_array:
    all_xor^=a
print(" ".join([str(all_xor^a) for a in a_array]))
N,M = list(map(int, input().split()))

combination = [1,1,2]
for i in range(3,N):
    combination.append(combination[i-1]+combination[i-2])

a = 0
ans = 1
lst = []

next_a = int(input())
lst.append(combination[next_a-a-1])
a = next_a

for i in range(M-1):
    next_a = int(input())
    if next_a-a == 1:
        ans = 0
        break
    lst.append(combination[next_a-a-2])
    a = next_a
    
next_a = N
lst.append(combination[next_a-a-1])

for tmp in lst:
    ans *= tmp
print(ans%1000000007)

### FIXED CODE ###

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

combination = [1,1,2]
for i in range(3,N+1):
    combination.append(combination[i-1]+combination[i-2])

a = 0
ans = 1
lst = []

if M > 0:
    next_a = int(input())
    lst.append(combination[next_a-a-1])
    a = next_a
    for i in range(M-1):
        next_a = int(input())
        if next_a-a == 1:
            ans = 0
            break
        elif next_a-a == 0:
            continue
        lst.append(combination[next_a-a-2])
        a = next_a

    next_a = N
    lst.append(combination[next_a-a-1])
else:
    lst.append(combination[N])
    
for tmp in lst:
    ans *= tmp
print(ans%1000000007)
import collections

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

a_counter=collections.Counter(a)
li=a_counter.most_common()[k:]
ans=0
for i in li:
    ans+=li(i)[1]
print(ans)


### FIXED CODE ###

import collections

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

a_counter=collections.Counter(a)
li=a_counter.most_common()[k:]
ans=0
for i in li:
    ans+=i[1]
print(ans)
a, b = map(str,input().split())
c = a + b
d = int(c)

for i in range(317):
  e = i * i
  print("No" if e > d)
  print("Yes" if e == d)

### FIXED CODE ###

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

i = 0

while i < 318:
  e = i * i
  if e == d:
    print("Yes"),
    i = 318
  else:
    if e > d:
      print("No")
      i = 318
    else:
      i = i +1
n=int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: x[1])
print(ab)
k=1
for t in range(n):
    k+=ab[t][0]
    print([k,answer])
    if k>ab[t][1]:
        answer=answer*0
if answer==1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n=int(input())
ab = [list(map(int, input().split())) for _ in range(n)]
ab.sort(key=lambda x: x[1])
#print(ab)
k=0
answer=1
for t in range(n):
    k+=ab[t][0]
    #print([k,answer])
    if k>ab[t][1]:
        answer=answer*0
if answer==1:
    print('Yes')
else:
    print('No')
def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=x//b;x,b=b,x%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()


### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

l = []
ans = 0
for t in [a,b,c,d,e]:
  if t%10 == 0:
    ans += t
  else:
    l.append(t)

if len(l) < 1:
  print(ans)10
elif len(l) == 1:
  print(ans + l[0])
else:
  l = sorted(l, key=lambda x: x%10, reverse=True)

  def tyumon(t, ans):
    ans += t
    if ans % 10 == 0:
      return ans
    else:
      return (ans//10 + 1)*10

  for i in range(len(l)-1):
    ans = tyumon(l[i], ans)
  print(ans + l[-1])

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

l = []
ans = 0
for t in [a,b,c,d,e]:
  if t%10 == 0:
    ans += t
  else:
    l.append(t)

if len(l) < 1:
  print(ans)
elif len(l) == 1:
  print(ans + l[0])
else:
  l = sorted(l, key=lambda x: x%10, reverse=True)

  def tyumon(t, ans):
    ans += t
    if ans % 10 == 0:
      return ans
    else:
      return (ans//10 + 1)*10

  for i in range(len(l)-1):
    ans = tyumon(l[i], ans)
  print(ans + l[-1])
a,b=map(int,input())
print(max(a*2-1,b*2-1,a+b))

### FIXED CODE ###

a,b=map(int,input().split())
print(max(a*2-1,b*2-1,a+b))
s = input()
t = ''
for c in s:
    if c = '1':
        t += '9'
    elif c = '9':
        t += '1'
print(t)


### FIXED CODE ###

s = input()
t = ''
for c in s:
    if c == '1':
        t += '9'
    elif c == '9':
        t += '1'
print(t)
# encoding:utf-8
N, K = LI()


ans = min(abs(N % K), abs(N % K - K), N)
print(ans)

### FIXED CODE ###

# encoding:utf-8
N, K = [int(i) for i in input().split()]
print(min(abs(N % K), abs(N % K - K), N))
import sys
from collections import defaultdict
from bisect import insort

n, m = map(int, input().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    sub = d[i]
    if len(sub) > 0:
        for j in range(len(sub)):
            insort(resList, sub[j])
    if len(resList) > 0:
        res += resList.pop()

print(res)


### FIXED CODE ###

import sys
from heapq import heappush,heappop

n, m = map(int, sys.stdin.readline().split())
d = [[] for _ in range(m+1)]
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    if a <= m:
        d[a].append(b)

res = 0
resList = []
for i in range(1, m+1):
    if len(d[i]) > 0:
        for j in d[i]:
            heappush(resList, -j)
    if len(resList) > 0:
        res += (-1) * resList[0]
        heappop(resList)

print(res)
def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = [[0 for i in range(LT + 1)] for j in range(LS + 1)]
  L = [[0 for i in range(LT)] for j in range(LS)]
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j]
      b = DP[i][j+1]
      c = DP[i][j] + 1
      if max(a, b) == a:
        DP[i+1][j+1] = a
        L[i][j] = 1
      else:
        DP[i+1][j+1] = b
        L[i][j] = 2
        a = b
      if s[i] == t[j]:
        if max(a, c) == c:
          DP[i+1][j+1] = c
          L[i][j] = 3       
        
  Ans = ""
  j = LS - 1
  k = LT - 1
  x = DP[j][k]
  for i in range(x, -1, -1):
    while True:
      if L[j][k] == 3:
        Ans += t[k]
        j -= 1
        k -= 1
        break
      elif L[j][k] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()


### FIXED CODE ###

def main(): 
  s = input()
  t = input()

  LS = len(s)
  LT = len(t)
      
  DP = [[0 for i in range(LT + 1)] for j in range(LS + 1)]
  L = [[0 for i in range(LT)] for j in range(LS)]
  for i in range(LS):
    for j in range(LT):
      a = DP[i+1][j]
      b = DP[i][j+1]
      if max(a, b) == a:
        DP[i+1][j+1] = a
        L[i][j] = 1
      else:
        DP[i+1][j+1] = b
        L[i][j] = 2
        a = b
      if s[i] == t[j]:
        c = DP[i][j] + 1
        if max(a, c) == c:
          DP[i+1][j+1] = c
          L[i][j] = 3       
        
  Ans = ""
  j = LS - 1
  k = LT - 1
  x = DP[LS][LT]
  for i in range(x, 0, -1):
    while True:
      if L[j][k] == 3:
        Ans += t[k]
        j -= 1
        k -= 1
        break
      elif L[j][k] == 2:
        j -= 1
      else:
        k -= 1
  print(Ans[::-1])
main()
m = map(int,raw_input().split())
if 0 <= m[3]-m[5]  and m[3]+m[5] <= m[1] and 0 <= m[4]-m[5] and m[4]+m[5] <= m[2]:
  print 'Yes'
else:
  print'No'

### FIXED CODE ###

m = map(int,raw_input().split())
if (0 <= m[2]-m[4])  and (m[2]+m[4] <= m[0]) and (0 <= m[3]-m[4]) and (m[3]+m[4] <= m[1]):
  print 'Yes'
else:
  print'No'
input = sys.stdin.readline
def main():
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]

    white, black = [], []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                black.append([i, j])
            else:
                white.append([i, j])

    ans = 0
    for bx, by in black:
        for wx, wy in white:

            queue = [[bx, by]]
            visited = [[False for i in range(w + 1)] for j in range(h+1)]
            while len(queue) != 0:
                p = queue.pop(0)
                visited[p[0]][p[1]] = True
                if p[0] == wx and p[1] == wy:
                    ans += 1
                    break
                for x, y in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                    nx = p[0] + x
                    ny = p[1] + y
                    if nx < 0 or ny < 0 or nx >= h or ny >= w or visited[nx][ny] == True:
                        continue
                    #print(nx, ny, s)
                    if (((nx+ny) % 2) == ((bx+by) % 2) and s[nx][ny] == ".") or (((nx+ny) % 2) != ((bx+by) % 2) and s[nx][ny] == "#"):
                        continue
                    queue.append([nx, ny])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from fractions import gcd
# from datetime import date, timedelta
from heapq import*
import math
from collections import defaultdict, Counter, deque
import sys
from bisect import *
import itertools
import copy
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7


def main():
    
    h, w = map(int, input().split())
    s = [list(input()) for i in range(h)]
    start = []
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#": 
                start.append([i,j])

    ans = [0,0]
    vis = [[-1 for i in range(w)] for j in range(h)]
    def f(x, y, pre):
        vis[x][y] = 1
        if s[x][y] == "#":
            ans[0] += 1
        else:
            ans[1] +=1
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            nx = i + x
            ny = j + y
            if nx >= 0 and ny >= 0 and nx < h and ny < w and vis[nx][ny] == -1:
                if pre == "B" and s[nx][ny] == ".":
                    f(nx,ny,"W")
                elif pre == "W" and s[nx][ny] == "#":
                    f(nx, ny, "B")
                
    
    ret = 0
    for i, j in start:
        if vis[i][j] == -1:
            f(i, j, "B")
        ret += ans[0] * ans[1]
        ans[0] = ans[1] = 0
    print(ret)
        

if __name__ == '__main__':
    main()
x,y,z = map(int,input().split())
print(z,x,y)

### FIXED CODE ###

a,b,c = input().split(",")
print(a,b,c)
t = input()
ans=ans.replace('P?','PD')
ans=t.replace('?D','PD')
ans=ans.replace('??','PD')
ans=ans.replace('?','D')
print(ans)

### FIXED CODE ###

t = input()
ans=t.replace('P?','PD')
ans=ans.replace('?D','PD')
ans=ans.replace('??','PD')
ans=ans.replace('?','D')
print(ans)
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, 1))
  e[v].append((u, 1))
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
dij = dijkstra(N, e)
s = 0
d = 0
p = dij.path(1, 0)
for i in range(1, N + 1):
  if p[i] > d:
    s = i
    d = p[i]
p = dij.path(s, 0)
mx = max(p[1: ])
dp = [-1] * (mx + 1)
dp[0] = 1
for i in range(mx):
  if i + 1 <= mx:
    if dp[i + 1] == -1 or (dp[i + 1] == ((dp[i] + 1) % 2)):
      dp[i + 1] = (dp[i] + 1) % 2
  if i + 2 <= mx:
    if dp[i + 2] == -1 or (dp[i + 2] == ((dp[i] + 1) % 2)):
      dp[i + 2] = (dp[i] + 1) % 2
if dp[-1]: print("Second")
else: print("First")

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
if N == 1:
  print("First")
  exit(0)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, 1))
  e[v].append((u, 1))
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
dij = dijkstra(N, e)
s = 0
d = 0
p = dij.path(1, 0)
for i in range(1, N + 1):
  if p[i] > d:
    s = i
    d = p[i]
p = dij.path(s, 0)
mx = max(p[1: ])
if mx % 3 == 1: print("Second")
else: print("First")
N = int(input())
X = input()

def calc(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    r_1 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % cnt
        a_1 = (a_1 * 2) % cnt

    return r_1[0]

def calc_first(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    a_2 = 1
    r_1 = [0] * (L+1)
    r_2 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % (cnt+1)
        r_2[i] = (r_2[i+1] + int(S[i]) * a_2) % (cnt-1)

        a_1 = (a_1 * 2) % (cnt + 1)
        a_2 = (a_2 * 2) % (cnt - 1)

    for i in range(L):
        if S[i] == "0":
            ans = (r_1[0] - r_1[i] + r_1[i+1] + pow(2, N-i-1, (cnt+1))) % (cnt+1)
        else:
            ans = (r_2[0] - r_2[i] + r_2[i+1]) % (cnt-1)

        cnt_ans = 1
        while ans > 0:
            ans = calc(str(bin(ans))[2:], len(str(bin(ans))[2:]))
            cnt_ans += 1
        print(cnt_ans)

calc_first(X, N)



### FIXED CODE ###

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

def calc(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    r_1 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % cnt
        a_1 = (a_1 * 2) % cnt

    return r_1[0]

def calc_first(S, L):
    cnt = 0
    for i in range(L):
        if S[i] == "1":
            cnt += 1

    a_1 = 1
    a_2 = 1
    r_1 = [0] * (L+1)
    r_2 = [0] * (L+1)
    for i in reversed(range(L)):
        r_1[i] = (r_1[i+1] + int(S[i]) * a_1) % (cnt+1)
        if cnt-1 > 0:
            r_2[i] = (r_2[i+1] + int(S[i]) * a_2) % (cnt-1)

        a_1 = (a_1 * 2) % (cnt + 1)
        if cnt-1 > 0:
            a_2 = (a_2 * 2) % (cnt - 1)

    for i in range(L):
        if S[i] == "0":
            ans = (r_1[0] - r_1[i] + r_1[i+1] + pow(2, N-i-1, (cnt+1))) % (cnt+1)
        else:
            if cnt == 1:
                print(0)
                continue
            else:
                ans = (r_2[0] - r_2[i] + r_2[i+1]) % (cnt-1)

        cnt_ans = 1
        while ans > 0:
            ans = calc(str(bin(ans))[2:], len(str(bin(ans))[2:]))
            cnt_ans += 1
        print(cnt_ans)

calc_first(X, N)