Harryxun/stf_run huggingface dataset:
n, q = map(int ,input().split())
s = list(input())
for i in range(q):
    l, r = map(int, input().split())
    ss = ''.join(s[l-1:r])
    ans = ss.count('AC')
    print(ans)

### FIXED CODE ###

s=list(input())
ans=0
for i in range(len(s)):
    for j in range(len(s)):
        ss=s[i:j+1]
        if len(ss)==ss.count('A')+ss.count('T')+ss.count('G')+ss.count('C'):
            cnt=len(ss)
            ans=max(ans,cnt)
print(ans)
import fractions
N = int(input())
A = list(map(int, input().split()))
AB = 1
for i in A:
    AB = AB*i//fractions.gcd(AB,i)
sumB = 0
for i in A:
    sumB += int(AB/i)
print(sumB%(10**9+7))

### FIXED CODE ###

import fractions
N = int(input())
A = list(map(int, input().split()))
AB = 1
for i in A:
    AB = AB*i//fractions.gcd(AB,i)
sumB = 0
for i in A:
    sumB += AB//i
print(int(sumB%(10**9+7)))
N = int(input())
A = list(map(int,input().split()))
l=0

for i in range(N):
    if A[i]>2*100000:
        A.remove(A[i])
N=len(A)
for i in range(N):
        for k in range(i+1 , N):
            if A[i]+A[k]==k-i or A[i]+A[k]==i-k:
                l+=1
print(l)

### FIXED CODE ###

name = input()
if name == "ARC":
    print("ABC")
else:
    print("ARC")
print(48-int(input()))

### FIXED CODE ###

A,B,C,D = map(int,input().split())
if A+B == C+D:
    print("Balanced")
elif A+B > C+D:
    print("Left")
else:
    print("Right")
n,m,x=map(int,input().split())
b=[0]*(N+1)
A=list(map(int,input().split()))
for a in A:
  b[a]=1
c=0
for i in range(x):
  c+=b[i]
print(n-c if c>=n-c else c)


### FIXED CODE ###

n,m,x=map(int,input().split())
b=[0]*(n+1)
A=list(map(int,input().split()))
for a in A:
  b[a]=1
c=0
for i in range(x):
  c+=b[i]
print(m-c if c>=m-c else c)
N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range[N]:
    ans = ans*A[i]

if ans<= 10**18:
    print(ans)
    exit(0)
else:
    print(-1)

### FIXED CODE ###

import sys  # sys.exit()を使いたいので

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

if 0 in a:
# 0が1つでもあれば0です
    print(0)
else:
# 0がない場合
    cur = 1  # 現在の数値
    for x in a:
        cur *= x
        if cur > 10 ** 18:
        # 10**18を超えたので終了します
            print(-1)
            sys.exit()
    print(cur)  # 10**18以下なので、出力します
N = int(input())
emp = list(map(int,input().split()))
for i in range(N):
    print(emp.count(i+1))
    emp.remove(i+1)


### FIXED CODE ###

N = int(input())
emp = list(map(int,input().split()))
ans_l = [0]*(N+1)
for i in range(N-1):
    a = emp[i]
    ans_l[a] +=1
for i in range(1,N+1):
    print(ans_l[i])
def calc(c1,c2,c3,c4):
    return c1*10 + c2*50 + c3*100 + c4*500

def coindiff(p,c1,c2,c3,c4):
    n = c1+c2+c3+c4
    over = calc(c1,c2,c3,c4) - p
    n -= (over%50) // 10
    n -= (over%100) // 50
    n -= (over%500) // 100
    n -= over // 500
    return n

while True:
    N = int(input())
    if N == 0: break
    c1,c2,c3,c4 = map(int,input().split())
    s1 = (N//10) % 5
    maxdiff = -9999999
    ans = None
    for n1 in range(s1,c1+1,5):
        for n2 in range(c2+1):
            for n3 in range(c3+1):
                rem = (N - n1*10 - n2*50 - n3*100)
                n4 = max(0, (rem-1)//500 + 1)
                d = coindiff(N,n1,n2,n3,n4)
                if d > maxdiff:
                    maxdiff = d
                    ans = {10:n1,50:n2,100:n3,500:n4}
    for k,v in sorted(ans.items()):
        if v == 0: continue
        print('{0} {1}'.format(k, v))
    print('')

### FIXED CODE ###

first = True
while True:
    P = int(input())
    if P== 0: break
    if first:
        first = False
    else:
        print('')
    c1,c2,c3,c4 = map(int,input().split())
    v = c1*10 + c2*50 + c3*100 + c4*500
    n = c1 + c2 + c3 + c4
    ans = {}
    rem = v - P
    ans[10] = c1 - (rem//10) % 5
    ans[50] = c2 - (rem//50) % 2
    ans[100] = c3 - (rem//100) % 5
    ans[500] = c4 - rem//500
    for k,v in sorted(ans.items()):
        if v <= 0: continue
        print('{0} {1}'.format(k,v))
from collections import defaultdict

N = int(input())
Ts = list(set([int(input()) for _ in range(N)]))

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    g = gcd(a, b)
    return a / g * b

res = Ts[0]
for T in Ts[1:]:
    res = lcm(res, T)
print(int(res))


### FIXED CODE ###

from collections import defaultdict

N = int(input())
Ts = list(set([int(input()) for _ in range(N)]))

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    g = gcd(a, b)
    return a // g * b

res = Ts[0]
for T in Ts:
    res = lcm(res, T)
print(int(res))
n = int(readline())
a = list(map(int, readline().split()))
max_l = max(a)
ans = 0
for i in range(n):
    if i == 0 and max_l:
        continue
    elif i < max_l:
        ans += 1
    else:
        ans = 0
print(ans)

### FIXED CODE ###

from sys import stdin
readline = stdin.readline
n = int(readline())
a = list(map(int, readline().split()))
x = 0
ans = 0
for i in a:
    if x > i:
        ans += (x-i)
    else:
        x = i
print(ans)
S = input()
sep = [0]
for i in range(len(S)-1):
    if S[i]=='<' and S[i+1]=='>': sep.append(i+1)
sep.append(i+2)

S += 'X'
ans = 0
center = 0
for i in range(len(sep)-1):
    s = S[sep[i]: sep[i+1]]
    l_max = s.count('>')
    ans += max(center, l_max)
    ans += l_max*(l_max-1)//2
    r_max = s.count('<')
    ans += r_max*(r_max-1)//2
    center = r_max

ans += center
print(ans)

### FIXED CODE ###

S = input()
sep = [0]
i=0
for i in range(len(S)-1):
    if S[i]=='<' and S[i+1]=='>': sep.append(i+1)
sep.append(i+2)

S += 'X'
ans = 0
center = 0
for i in range(len(sep)-1):
    s = S[sep[i]: sep[i+1]]
    l_max = s.count('>')
    ans += max(center, l_max)
    ans += l_max*(l_max-1)//2

    r_max = s.count('<')
    ans += r_max*(r_max-1)//2
    center = r_max

ans += center
print(ans)
N = int(input())
H = list(map(int, input().split()))
a = [0] * N

for i in range(N):
  for j in range(i:N-1):
    if H[j] >= H[j+1]:
      a[i] = a[i] + 1
    else:
      break
      
print(max(a))

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
a = [0] * N
start = 0

for i in range(N - 1):
  if H[i] >= H[i+1]:
    a[start] += 1
  else:
    start += 1

      
print(max(a))
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd

mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=limii()

if n==1:
    print((arr[i]-1)**2)
    exit()

ans = int(sum(arr)//n)+1
cnt=0
for i in range(n):
    cnt+=(ans-arr[i])**2

print(cnt)






### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=limii()

if n==1:
    print(0)
    exit()

ans = Decimal(str(sum(arr)/n)).quantize(Decimal("0"),rounding=ROUND_HALF_UP)
cnt=0
for i in range(n):
    cnt+=(ans-arr[i])**2

print(cnt)
s = input()
k = int(input())
ans = 0
soui = 0
moji = s[1]

for i in range(1,len(s)):
    if s[i] == s[i-1] and soui == 0:
        ans += 1
        soui = 1
    elif soui == 1:
        soui = 0

flag = 0

if s[0] == s[len(s)-1] and soui == 0:
    ans += 1
    flag = 1

for i in range(len(s)):
    if moji != s[i]:
        break
    elif i == len(s)-1:
        flag = 2

if flag == 1:
    print((k*ans)-1)
elif flag == 2:
    print((k*len(s))//2)
else:
    print(k*ans)


### FIXED CODE ###

s = input()
k = int(input())
ans = 0
soui = 0
moji = s[0]

for i in range(1,len(s)):
    if s[i] == s[i-1] and soui == 0:
        ans += 1
        soui = 1
    elif soui == 1:
        soui = 0


flag = 0
a = 0
b = 0

while s[0] == s[a] and a != len(s)-1:
    a += 1

while s[len(s)-1-b] == s[len(s)-1] and b != len(s)-1:
    b += 1


if s[0] == s[len(s)-1]:
    flag = 1

for i in range(len(s)):
    if moji != s[i]:
        break
    elif i == len(s)-1:
        flag = 2

if flag == 1:
    print((k*ans)-((k-1)*((a//2)+(b//2)-((a+b)//2))))
elif flag == 2:
    print((k*len(s))//2)
else:
    print(k*ans)
import sys
import fractions
a, b = map(int, sys.stdin.raedline())
gcd = fractions.gcd(a, b)
print(a * b // gcd)

### FIXED CODE ###

import sys
import fractions
a, b = map(int, sys.stdin.readline().split())
gcd = fractions.gcd(a, b)
print(a * b // gcd)
# B
s = list(input())

count = 0
l = []
for i in range(len(s)):
    if s[i] == 'A':
        count += 1
        continue
    elif s[i] == 'C':
        count += 1
        continue
    elif s[i] == 'G':
        count += 1
        continue
    elif s[i] == 'T':
        count += 1
        continue
    else:
        l.append(count)
        count = 0

print(max(l))

### FIXED CODE ###

# B
s = list(input())

count = 0
l = []
for i in range(len(s)):
    if s[i] == 'A':
        count += 1
        continue
    elif s[i] == 'C':
        count += 1
        continue
    elif s[i] == 'G':
        count += 1
        continue
    elif s[i] == 'T':
        count += 1
        continue
    else:
        l.append(count)
        count = 0
l.append(count)

print(max(l))
find / -name pip

### FIXED CODE ###

import sys, collections
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N = I()
    A = LI()

    cnt = collections.Counter(A)
    A = list(set(A))
    A.sort()
    A_max = A[-1]
    divisible = [False] * (A_max + 1)

    for i in A:
        for j in range(2 * i, A_max+1, i):
            divisible[j] = True

    ans = 0
    for i in A:
        tmp = 0
        if not divisible[i] and cnt[i] == 1:
            tmp += 1
        ans += tmp

        
    print(ans)

if __name__ == '__main__':
    resolve()
a,b,c,d=input()

print("Yes" if a=b=c or b=c=d else "No")

### FIXED CODE ###

l = input()

print("Yes" if l[0]==l[1]==l[2] or l[1]==l[2]==l[3] else "No")
import bisect
n,k = map(int,input().split())
x = list(map(int,input().split()))
bindex = bisect.bisect_left(x,0)
mainasu = x[:bindex] #[-30,-20,-10]
purasu = x[bindex:] #[10,20,30]
"""
for i in range(len(mainasu)-2,-1,-1): #0は対象ではない
  mainasu[i] = mainasu[i+1]+mainasu[i]
#[-60,-30,-10]
for i in range(1,len(purasu)):
  purasu[i] = purasu[i-1]+purasu[i]
#[10,30,60]
"""
ans = 10**9
if len(mainasu) >= k:
  ans = min(ans,abs(mainasu[-k]))
if len(purasu) >= k:
  ans = min(ans,purasu[k-1])

for i in range(len(mainasu)-k,len(mainasu)): #-2~2
  if i >= len(purasu):break
  a = abs(mainasu[i])
  b = purasu[i]
  ans = min(ans,a*2+b,a+b*2)
print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
x = list(map(int,input().split()))
l,r = 0,0
anus = 10**9
for i in range(n):
  l = i
  r = i+(k-1)
  if r >= n:
    break
  anus = min(anus,abs(x[l])+abs(x[r]-x[l]),abs(x[r])+abs(x[r]-x[l]))
print(anus)
from math import randint()
for i in range(365):
  print(randint(1,26))

### FIXED CODE ###

D = int(input())
c = list(map(int,input().split()))
s = [list(map(int,input().split())) for i in range(D)]

last = {}
for i in range(1,27):
    last[i] = 0

for d in range(1,D+1):
    ans = [1,0]
    for i in range(1,27):
        satisfaction = 0
        satisfaction += s[d-1][i-1]
        for j in range(1,27):
            if i != j:
                satisfaction -= c[j-1]*(d-last[j])
        if ans[1] <= satisfaction:
            ans = [i,satisfaction]
    last[ans[0]] = d
    print(ans[0])
import math
A, B = map(int, input().split())
digit_A = math.ceil(math.log2(A))
digit_B = math.ceil(math.log2(A))
result = A
for i in range(A+1, 2 ** digit_A):
    result = result ^ i
for i in range(2 ** (digit_B-1), B + 1):
    result = result ^ i
print(result)

### FIXED CODE ###

A, B = map(int, input().split())
if A % 2 == 0:
    num = B - A
    result = 0
else:
    num = (B - (A + 1))
    result = A
if num // 2 % 2 == 0:
    result ^= 0
else:
    result ^= 1
if num % 2 == 1:
    result ^= (B-1)
result ^= B
print(result)
n = int(input())

n1 = list(map(int,input().split()))

sum = 1
for i in n1:
    sum *= i
    if sum > 10 ** 18:
        print('-1') 
        break

print(sum)

### FIXED CODE ###

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

print(a * b)
import sys
lines = sys.stdin.readlines()
for i in range(lines):
    a = int(lines[i])
    if(a == 0):
        break
    else:
        print("Case {0}: {1}".format(i+1, a))


### FIXED CODE ###

import sys
lines = sys.stdin.readlines()
for i in range(len(lines)):
    a = int(lines[i])
    if(a == 0):
        break
    else:
        print("Case {0}: {1}".format(i+1, a))
from fractions import gcd
def fun():
    nx = input()
    N, X = nx.split(' ')
    N = int(N)
    X = int(X)
    cities = [int(c) for c in input().split(' ')]
    cities.append(X)
    x = sorted(cities)
    nx = x[1:]
    dist = [nn - x[i] for i, nn in enumerate(nx)]
    if N==1:
        print(dist[0])
        return
    min_gcd = 10000000000
    for i, d in enumerate(dist[:-1]):
        dp = dist[i+1]
        gc = gcd(d, dp)
        if gc < min_gcd:
            min_gcd = gc
    print(min_gcd)

fun()


### FIXED CODE ###

s = input()
a,b = s.split(' ')
a = int(a)
b = int(b)
if (a%2 == 0) or (b%2 == 0):
    print('No')
else:
    print('Yes')
H, W = map(int, input().split())
for i in range(H):
s = input()
    print(s)
    print(s)



### FIXED CODE ###

H, W = map(int, input().split())
for _ in range(H):
    s = input()
    print(s)
    print(s)
A,B = map(int,input().split())

if A >= B:
  print(1)
  
else:
 
  for i in list(range(1,21)):
    if (A-1) * i + A >= B:
      print(i+1)
      break
      

### FIXED CODE ###

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

sat = 0
for a,b in zip(A,A[1:]):
  if b == a+1:
    sat += C[a-1]
    
print( sum(B) + sat )
from collections import Counter

N, K = map(int, input().split())
input_list = [[int(i) for i in input().split()] for j in range(N)]
input_list.sort()

input_counter = Counter()

for element in input_list:
    input_counter[element[0]] += element[1]

for element in input_list:
    K -= element[1]
    if K <= 0:
        print(element[0])
        break

### FIXED CODE ###

from collections import Counter

N = int(input())

count_counter = Counter()
result = 0
over = 0

for i in input().split():
    count_counter[int(i) // 400] += 1

for key in count_counter.keys():
    if key < 8:
        result += 1
    else:
        over += count_counter[key]

if result == 0:
    print(1, over)
else:
    print(result, result+over)
N, M = [int(x) for x in input().split()]

P = [0] * (N + 1)
correct = 0
ok = [False] * (N + 1)
for i in range(M):
    query = input().split()
    p = int(query[0])
    S = query[1]
    if ok[p] == False:
        if S == 'AC':
            ok[p] = True
            correct += 1
        else: # S = 'WA'
            P[p] += 1

penalty = 0
for i in range(N):
    if ok[p] == True:
        penalty += P[p]

print(correct, end=' ')
print(penalty)

### FIXED CODE ###

N, M = [int(x) for x in input().split()]

P = [0] * (N + 1)           #各問題のペナルティの回数を記録
ok = [False] * (N + 1)      #その問題でACが出たかどうか記録

correct = 0                 #正答数を記録
penalty = 0                 #ペナルティ数を記録
for i in range(M):
    query = input().split()
    p = int(query[0])
    S = query[1]
    if ok[p] == False:
        if S == 'AC':
            ok[p] = True
            correct += 1
            penalty += P[p]
        else: # S = 'WA'
            P[p] += 1

print(correct, end=' ')
print(penalty)
A,B,C = map(int,input().split())
if (A-B) >= C:
	print(0)
else:
  prnt(C-(A-B))
  

### FIXED CODE ###

A,B,C = map(int,input().split())
if (A-B) >= C:
	print(0)
else:
 	print(C-(A-B))
import fractions
A, B = map(int, input().split())
GCD = fractions.gcd(A, B)
def eratosthenes(limit):
  E = [1] * (limit + 1)
  E[0], E[1] = 0, 0
  prime_table = []
  for i, e in enumerate(E):
    if e == 0:
      continue
    prime_table.append(i)
    for j in range(i, limit + 1, i):
      E[j] = 0
  return prime_table
P = eratosthenes(GCD)
print(len([p for p in P if GCD % p == 0]) + 1)

### FIXED CODE ###

import fractions
A, B = map(int, input().split())
GCD = fractions.gcd(A, B)
k = 1
cnt = 1
while GCD > 1:
  k += 1
  if k ** 2 > GCD:
    cnt += 1
    break
  if GCD % k:
    continue
  cnt += 1
  while GCD % k == 0:
    GCD //= k
print(cnt)
s=input()
ans=0
for i in range(len(s)//2)-1:
	if s[i]!=s[len(s)-1-i]:
		ans+=1
print(ans)

### FIXED CODE ###

s=input()
ans=0
for i in range(len(s)//2):
	if s[i]!=s[len(s)-1-i]:
		ans+=1
print(ans)
A=int(input())
B=int(input())
C=int(input())
while A<1 or A>100 or B<1 or B>100 or C<1 or C>100:
	A=int(input())
    B=int(input())
    C=int(input())
D=B//A-C
if D>0:
  print(C)
else:
  print(B//A)


### FIXED CODE ###

A,B,C=map(int,input().split())
D=B//A-C
if D>0:
  print(C)
else:
  print(B//A)
import collections

def printCircuit(v):
  edge_count=[0]*(n+1)
  for i in range(1,n+1):
    edge_count[i]=len(g[i])
  curr_path=collections.deque()
  circuit=[]
  curr_path.appendleft(v)
  curr_v=v
  while len(curr_path)!=0:
    if edge_count[curr_v]:
      curr_path.appendleft(curr_v)
      next_v=g[curr_v].pop(-1)
      g[next_v].remove(curr_v)
      edge_count[curr_v]-=1
      edge_count[next_v]-=1
      curr_v=next_v
    else:
      circuit.append(curr_v)
      curr_v=curr_path.popleft()
  return circuit

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
cnt=[0]*(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
  cnt[a]+=1
  cnt[b]+=1
cnt1=0
cnt2=0
cand=[]
for i in range(1,n+1):
  if cnt[i]%2==0:
    cnt1+=1
  else:
    cnt2+=1
    cand.append(i)
if m%2==1:
  print(-1)
  else:
  if cnt1==n:
    path=printCircuit(1)
    if len(path)%2==1:
      for i in range(len(path)):
        if i%2==1:
          print(path[i],path[i-1])
          print(path[i],path[i+1])
    else:
      print(-1)
  elif cnt1==n-2 and cnt2==2:
    if len(g[cand[0]])==1:
      c=cand[0]
    else:
      c=cand[1]
    path=printCircuit(c)
    if len(path)%2==1:
      for i in range(len(path)):
        if i%2==1:
          print(path[i],path[i-1])
          print(path[i],path[i+1])
    else:
      print(-1)
  else:
    print(-1)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def dfs1(v):
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      g2[v].append(u)
      g3[v].append(u)
      g3[u].append(v)
      dfs1(u)
      
def dfs2(v):
  for u in g2[v]:
    if checked[u]==0:
      checked[u]=1
      dfs2(u)
      if cnt[u]%2==1:
        ans.append((u,v))
        cnt[u]+=1
      else:
        ans.append((v,u))
        cnt[v]+=1
      
n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
g2=[[] for _ in range(n+1)]
g3=[[] for _ in range(n+1)]
cnt=[0]*(n+1)
ans=[]
ansset=set()
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
if m%2==1:
  print(-1)
else:
  checked=[0]*(n+1)
  checked[1]=1
  dfs1(1)
  for v in range(1,n+1):
    for u in g[v]:
      if u not in g3[v]:
        if (u,v) not in ansset:
          ans.append((v,u))
          ansset.add((v,u))
          cnt[v]+=1
  checked=[0]*(n+1)
  checked[1]=1
  dfs2(1)
  for v,u in ans:
    print(v,u)
n=int(input())

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

one_cnt=s.count("1")

modp=[0]*n
modm=[0]*n

for i in range(n):
    modp[i]=(pow(2,(n-i-1),one_cnt+1)*int(s[i]))%(one_cnt+1)
    modm[i]=(pow(2,(n-i-1),one_cnt-1)*int(s[i]))%(one_cnt-1)

ans=[]
memo_one=[0]*(n+1)

#print(modp,modm)

for i in range(n):
    cnt=0
    mod=0

    for j in range(n):
        if s[i]=="1":
            if i!=j:
                mod=(mod+modm[j])%(one_cnt-1)
        else:
            if i!=j:
                mod=(mod+modp[j])%(one_cnt+1)
            else:
                mod=(mod+2**(n-i-1))%(one_cnt+1)
    cnt=1

   # print(i,mod)

    if mod==0:
        ans.append(cnt)
    else:
        while 1:
            cnt+=1
            if memo_one[mod]!=0:
                mod=mod%(memo_one[mod])
            else:
                tmp=(bin(mod).count("1"))
                memo_one[mod]=tmp
                mod=mod%(tmp)
            if mod==0:
                ans.append(cnt)
                break
            #print(mod,one_cnt,s[i],cnt)




#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)