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

import sys
from collections import deque

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, M = na()
node_dic = {}
no_in = [1] * N

for _ in range(M):
    x, y = na()
    if x-1 in node_dic:
        node_dic[x-1].append(y-1)
    else:
        node_dic[x-1] = [y-1]
    no_in[y-1] = 0


# print(node_dic, no_in)


ans_array = [0] * N

edge = deque([])

for i, x in enumerate(no_in):
    if x == 1:
        deque.append(edge, i)

while(len(edge)):
    e = deque.popleft(edge)
    if e in node_dic:
        for x in node_dic[e]:
            deque.append(edge, x)
            ans_array[x] = max(ans_array[x], ans_array[e] + 1)
    # print(ans_array)
print(max(ans_array))

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def cal(e):
    if ans_array[e] != -1:
        return ans_array[e]
    ans = 0
    if e in node_dic:
        for x in node_dic[e]:
            ans = max(ans, cal(x) + 1)
    ans_array[e] = ans
    return ans


N, M = na()
node_dic = {}
no_in = [1] * N

for _ in range(M):
    x, y = na()
    if x-1 in node_dic:
        node_dic[x-1].append(y-1)
    else:
        node_dic[x-1] = [y-1]
    no_in[y-1] = 0


# print(node_dic, no_in)


ans_array = [-1] * N

edge = deque([])

for i, x in enumerate(no_in):
    if x == 1:
        cal(i)


print(max(ans_array))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    

n,m=map(int,input().split())
p=[int(i)-1 for i in input().split()]
tree=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    tree.union(x-1,y-1)

ans=0
for i in range(n):
    #print(p[i],tree.members(i))
    if p[i] in tree.members(i):
        ans+=1
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
    

n,m=map(int,input().split())
p=[int(i)-1 for i in input().split()]
tree=UnionFind(n)
for _ in range(m):
    x,y=map(int,input().split())
    tree.union(x-1,y-1)

ans=0
for i in range(n):
    #print(p[i],tree.members(i))
    if tree.same(p[i],i):
        ans+=1
print(ans)
### BUGGY CODE ###

import numpy as np


def count_multi(s, d):
  a = np.array([int(c) for c in s])  # .astype(np.int)
  m = a
  keta = 1
  count = np.count_nonzero(m == 0)
  while len(m) > 1:
    m = (m[:-1]*10 + a[keta:]) % d
    keta += 1
    count += np.count_nonzero(m == 0)
  return count
        
print(count_multi(input().strip(), 2019))


### FIXED CODE ###

def main():
    mod = 2019
    count = [0] * 2019
    count[0] = 1
    s = input().strip()
    digit = 1
    current = 0
    for c in s[::-1]:
        current = (current + int(c) * digit) % mod
        count[current] += 1
        digit = digit * 10 % mod
    return sum([n * (n - 1) // 2 for n in count if n > 1])


print(main())
### BUGGY CODE ###

from itertools import permutations
N = int(input())
nums = list(map(int, input().split()))

useable_nums = set(nums)

# print(nums)
# print(useable_nums)

inf = float('inf')
min_ans = inf
if len(useable_nums) == 1:
    useable_nums.add(list(useable_nums)[0] + 1)
useable_permutaions = permutations(useable_nums, 2)
# print(useable_permutaions)
# print(list(useable_permutaions))
# print(list(useable_permutaions))
for permutation in useable_permutaions:
    ans = 0
    for i, num in enumerate(nums):
        if i % 2 == 0:
            if permutation[0] != num:
                # print(num, i, permutation[0])
                ans += 1
        else:
            if permutation[1] != num:
                # print(num, i, permutation[1])
                ans += 1
    # print(permutation, ans)
    min_ans = min(min_ans, ans)

print(min_ans)


### FIXED CODE ###

from itertools import permutations
import collections
N = int(input())
nums = list(map(int, input().split()))
odd_nums = []
even_nums = []
for i, num in enumerate(nums):
    if i % 2 == 1:
        even_nums.append(num)
    else:
        odd_nums.append(num)

useable_nums = set(nums)
even_length = len(even_nums)
odd_length = len(odd_nums)
even_counter = collections.Counter(even_nums).most_common()
odd_counter = collections.Counter(odd_nums).most_common()
even_counter.append((0, 0))
odd_counter.append((0, 0))
even_counter.sort(key=lambda x: x[1], reverse=True)
odd_counter.sort(key=lambda x: x[1], reverse=True)
# print(even_counter)
# print(odd_counter)


min_ans = None
if even_counter[0][0] == odd_counter[0][0]:
    min_ans = min((odd_length - odd_counter[0][1]) + (even_length - even_counter[1][1]),
                  (odd_length - odd_counter[1][1]) + (even_length - even_counter[0][1]))
else:

    min_ans = odd_length - odd_counter[0][1] + even_length - even_counter[0][1]
print(min_ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
AL=defaultdict(lambda: set())
IN=defaultdict(lambda: 0)


for i in range(N):
	A=map(int, sys.stdin.readline().split())
	for j in range(N-2):
		x=i+1
		x_next=i+1
		y_now=A[j]
		y_next=A[j+1]
		#print x,y_now,x_next,y_next
		if x>y_now: x,y_now=y_now,x
		if x_next>y_next: x_next,y_next=y_next,x_next
		IN[(x_next,y_next)]+=1
		AL[(x,y_now)].add((x_next,y_next))

q=deque()

for i in range(1,N+1):
	for j in range(i+1,N+1):
		if IN[(i,j)]==0:
			q.append((i,j))


DAY=defaultdict(lambda: 1)	#距離
Visit=defaultdict(lambda: None)

while q:
	fro=q.pop()
	for to in AL[fro]:
		alt=DAY[fro]+1
		if DAY[to]<alt:
			DAY[to]=max(DAY[to],DAY[fro]+1)
			q.append((to[0],to[1]))

try:
	print max(DAY.values())
except:
	print -1

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
from collections import defaultdict,deque

N=input()
A=[[]]+[ map(int, sys.stdin.readline().split()) for _ in range(N) ]
C=defaultdict(lambda: 0)

Now=[ 0 for _ in range(N+1)]
game=set()
next_game=set()

for i in range(1,N+1):
	a=i
	b=A[i][0]
	if a>b: a,b=b,a
	game.add((a,b))

day=0

while game:
	next_game=set()
	Visit=defaultdict(lambda: None) 

	for x,y in game:
		now_x=Now[x]
		now_y=Now[y]

		xopp=A[x][now_x]
		yopp=A[y][now_y]

		if (x,y)==(yopp,xopp) and Visit[x] is None and Visit[y] is None:
			Visit[x]=1
			Visit[y]=1
			if now_x<N-2:
				now_x+=1
				Now[x]=now_x
				x_nextopp=A[x][now_x]
				if x_nextopp<x: x,x_nextopp=x_nextopp,x
				next_game.add((x,x_nextopp))

			if now_y<N-2:
				now_y+=1
				Now[y]=now_y
				y_nextopp=A[y][now_y]
				if y_nextopp<y: y,y_nextopp=y_nextopp,y
				next_game.add((y,y_nextopp))

	game=next_game
	day+=1


for i in range(1,N+1):
	if Now[i] != N-2:
		print -1
		quit()
else:
	print day
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append((sx,sy))
  while d:
    x,y=d.popleft()
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      b[x-i][y]=b[x][y]+1
      d.append((x-i,y))
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      b[x+i][y]=b[x][y]+1
      d.append((x+i,y))
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      b[x][y-j]=b[x][y]+1
      d.append((x,y-j))
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      b[x][y+j]=b[x][y]+1
      d.append((x,y+j))
  print(-1)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

import sys
from collections import deque
input = sys.stdin.readline

STEPS = [
    (0, 1),
    (1, 0)
]
BLACK = '#'
WHITE = '.'
CHECKED = 't'

def main():
    H, W = map(int, input().split())
    board = [list(input().strip()) for _ in range(H)]

    ans = float('INF')

    if board[0][0] == WHITE:
        que = deque([[0, 0, WHITE, 0]])
    else:
        que = deque([[0, 0, BLACK, 1]])


    while que:
        y, x, color, rev = que.popleft()

        for (i,j) in STEPS:
            ny, nx = y + i, x + j
            if ny >= H or nx >= W:
                continue

            n_rev = rev
            target = board[ny][nx]

            if color == WHITE and target == BLACK:
                n_rev += 1

            if ny == H -1 and nx == W - 1:
                ans = min(ans, n_rev)

            que.append([ny, nx, target, n_rev])

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline

STEPS = [
    (0, 1),
    (1, 0)
]
BLACK = '#'
WHITE = '.'
CHECKED = 't'
INF = float('INF')

def main():
    H, W = map(int, input().split())
    board = [list(input().strip()) for _ in range(H)]
    scores = [[INF] * W for _ in range(H)]


    if board[0][0] == WHITE:
        scores[0][0] = 0
    else:
        scores[0][0] = 1

    que = deque([[0, 0, board[0][0]]])


    while que:
        y, x, color = que.popleft()
        score = scores[y][x]

        for (i,j) in STEPS:
            ny, nx = y + i, x + j
            if ny >= H or nx >= W:
                continue

            target = board[ny][nx]
            n_score = score

            if color == WHITE and target == BLACK:
                n_score += 1

            if n_score < scores[ny][nx]:
                scores[ny][nx] = n_score
                que.append([ny, nx, target])

    print(scores[H-1][W-1])


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

n = int(input())

up = int((n//2)**.5)
mp = set(p for p in range(3, up + 1, 2))
mp.add(2)
for i in range(3, up+1, 2):
    #if mp[i] == False:
    if i not in mp:
        continue
    j = 2
    while i*j < up:
        if i*j in mp:
            mp.remove(i*j)
        j += 1
ps = mp

# -----------------------------
mp = {p:1 for p in ps}

ops = 0
while n != 1:
    for p in ps:
        if p > n:
            break

        e = mp[p]
        z = p**e
        if n % p == 0:
            if n % z == 0:
                #print('new ops')
                #print(p, e, n//z)
                n //= z
                mp[p] += 1
                ops += 1
            else:
                #print('shadow ops')
                while n % p == 0:
                    n //= p
                # no ops

print(ops)

### FIXED CODE ###

n = int(input())

mp = {}
for f in range(2, 1000000):
    while n % f == 0:
        mp[f] = 1 if f not in mp else mp[f] + 1
        n //= f
if n > 1:
    mp[n] = 1

def fn(x):
    for i in range(2, 100):
        sm = i*(i+1)//2
        if x < sm:
            return i - 1

#print(mp)
#print({p:fn(mp[p]) for p in mp})
print(sum(fn(mp[p]) for p in mp))
### BUGGY CODE ###

import copy
import math

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():
    n = get_int()
    s_list = get_string_char_list()
    #ans_set = set([])

    #for i in range(0,n):
    #    for ii in range(i+1, n):
    #        for iii in range(ii+1, n):
    #            ans_set.add(int(s_list[i]) * 100 + int(s_list[ii]) * 10 + int(s_list[iii]) * 1)

    #print(len(ans_set))

    ans = 0

    for i in range(0, 1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10

        find_a = False
        find_b = False
        for ii in range(0, n):

            if (find_a == False) and (s_list[ii] == str(a)):
                find_a = True
            elif (find_a == True) and (find_b == False) and (s_list[ii] == str(b)):
                find_b = True
            elif (find_a == True) and (find_b == True) and (s_list[ii] == str(c)):
                ans += 1
                break
    print(ans)

if __name__ == '__main__':
    main()




### FIXED CODE ###

import copy
import math
import time

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():
    start = time.time()

    n = get_int()
    s_list = get_string_char_list()
    s_list = [int(x) for x in s_list]

    #n = 30000
    #s_list = [1] * 30000

    #ans_set = set([])

    #for i in range(0,n):
    #    for ii in range(i+1, n):
    #        for iii in range(ii+1, n):
    #            ans_set.add(int(s_list[i]) * 100 + int(s_list[ii]) * 10 + int(s_list[iii]) * 1)

    #print(len(ans_set))

    ans = 0

    for i in range(0, 1000):
        a = i // 100
        b = (i % 100) // 10
        c = i % 10

        find_a = False
        find_b = False
        for ii in s_list:

            if (find_a == False) and (ii == a):
                find_a = True
            elif (find_a == True) and (find_b == False) and (ii == b):
                find_b = True
            elif (find_b == True) and (ii == c):

                ans += 1
                break
    print(ans)

    #print(time.time() - start)

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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


def calc_sum(a_binary, n_1_ls, n_1_max):
    '''
    a_binaryはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (((2**i) % MOD) * (n_1 % MOD)) % MOD
        else:
            ret += (((2**i) % MOD) * ((n_1_max - n_1) % MOD)) % MOD
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
a_pre = A[N - 1]
a_pre_binary = ret_binary(a_pre)
for a in A[-2::-1]:
    a_binary = ret_binary(a)
    n_1_ls = add_koko(n_1_ls, a_pre_binary)
    n_1_max += 1
    tmp = calc_sum(a_binary, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD
    a_pre_binary = a_binary

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        S = S[::-1]
    else:
        if query[1] == '1':
            S = query[2] + S
        else:
            S = S + query[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
bs = ''
fs = ''
hanten = 0
for i in range(Q):
    query = list(input().split())
    if query[0] == '1':
        hanten += 1
    else:
        if query[1] == '1':
            if hanten % 2 == 0:
                fs += query[2]
            else:
                bs += query[2]
        else:
            if hanten % 2 == 0:
                bs += query[2]
            else:
                fs += query[2]
if hanten % 2 == 0:
    print(fs[::-1]+S+bs)
else:
    print(bs[::-1]+S[::-1]+fs)
### BUGGY CODE ###

import sys
read = sys.stdin.read
#readlines = sys.stdin.readlines
from collections import defaultdict
from copy import deepcopy
def main():
    def from10to2(p):
        res = []
        while p:
            p, t = divmod(p, 2)
            res.append(str(t))
        return "".join(res[::-1])

    def from2to10(p):
        res = 0
        num2 = 1
        for c in p[::-1]:
            if c == '1':
                res += num2
            num2 *= 2
        return res

    def f(p):
        if p == 0:
            return 0
        elif d1[p] > 0:
            return d1[p]
        else:
            ppop = from10to2(p).count('1')
            p2 = p % ppop
            fp = f(p2) + 1
            d1[p] = fp
            return fp

    n = int(input())
    x = list(input())

    d1 = defaultdict(int)
    d1[0] = 0
    for i1 in range(n):
        tx = deepcopy(x)
        if tx[i1] == '1':
            tx[i1] = '0'
        else:
            tx[i1] = '1'
        t = from2to10(tx)
        print(f(t))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
from collections import defaultdict
def main():
    n = int(input())
    x = list(input())
    # 0除算よけ。
    if n == 1:
        if x[0] == '1':
            print(0)
        else:
            print(1)
        sys.exit()
    # xの10進数換算と１の数カウント。
    x10 = int("".join(x), 2)
    xcount1 = x.count('1')
    # 2**i(mod 1の数)をケースごとに用意する。
    mod2plus = [0] * n
    mod2plus[0] = (1 % (xcount1+1)) # 必ず1になる。xcount1=0はありえない。
    for j1 in range(1, n):
        mod2plus[j1] = (mod2plus[j1 - 1] * 2) % (xcount1+1)
    mod2minus = [0] * n
    if xcount1 > 1:
        mod2minus[0] = 1
        for j1 in range(1, n):
            mod2minus[j1] = (mod2minus[j1 - 1] * 2) % (xcount1-1)
    # x(mod 1の数)をケースごとに用意する。
    modx_plus = x10 % (xcount1 + 1)
    if xcount1 == 1:
        modx_minus = 0
    else:
        modx_minus = x10 % (xcount1 - 1)
    popcount = defaultdict(int)
    for i1 in range(n):
        if x[i1] == '1':
            if xcount1 == 1:
                print(0)
                continue
            else:
                x3 = modx_minus - mod2minus[n - 1 - i1]
                if x3 < 0:
                    x3 += (xcount1 - 1)
                elif x3 > (xcount1 - 1):
                    x3 -= (xcount1 - 1)
                elif x3 == (xcount1 - 1):
                    print(1)
                    continue
        else:
            x3 = modx_plus + mod2plus[n - 1 - i1]
            if x3 < 0:
                x3 += (xcount1 + 1)
            elif x3 > (xcount1 + 1):
                x3 -= (xcount1 + 1)
            elif x3 == (xcount1 + 1):
                print(1)
                continue
        r = 1
        while x3:
            r += 1
            if popcount[x3] == 0:
                p = bin(x3).count('1')
                popcount[x3] = p
                x3 = x3 % p
            else:
                x3 = x3 % popcount[x3]
        print(r)

if __name__ == '__main__':
    main()