CodeEff/ECCO huggingface dataset:
# Original solution
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from functools import lru_cache


@lru_cache(maxsize=2*10**5)
def f2(x):
    if x == 0: return 0
    y = bin(x).count("1")
    return 1 + f2(x % y)

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()


# Optimized solution
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = input()
    cnt0 = S.count("1")

    if cnt0 == 0:
        print(*[1]*N, sep="\n")
        return

    X = int(S, 2)

    def f2():
        cache = [-1] * max(9, cnt0+1)
        cache[0] = 0
        for i in range(3): cache[1<<i] = 1
        def f2(x):
            if cache[x] != -1:
                #hit[x] += 1
                return cache[x]

            y = bin(x).count("1")
            z = 1 + f2(x % y)
            cache[x] = z

            return z
        f2.cache = cache
        return f2
    f2 = f2()

    dc = {}
    for k, v in (("0", 1), ("1", -1)):
        x = cnt0 + v
        y = X % x if x else 0
        dc[k] = (x, v, y, [1, N-1])

    ans = [0] * N
    for i in reversed(range(N)):
        si = S[i]
        cnt, v, n, m1 = dc[si]

        if cnt == 0:
            ans[i] = 0
            continue

        ni = N - i - 1
        m2 = (m1[0]<<(m1[1]-i)) % cnt
        n = (n + v*m2) % cnt
        m1[0] = m2; m1[1] = i

        ans[i] = 1 + f2(n)

    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()
# Original solution
n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(q):
    c = 0
    while q:
        q, r = divmod(q, 2)
        c += r
    return c

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print((0))
        else:
            print((dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1))
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print((dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1))
        else:
            print((dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1))

# Optimized solution
n, X = open(0).read().split()
n = int(n)
x = int(X, 2)
X = list(map(int, X))

def popcount(n):
    return bin(n).count('1')

ma = 2 * 10**5 + 1
dp = [0] * ma
for i in range(1, ma):
    dp[i] = dp[i % popcount(i)] + 1

c = popcount(x)
a = x % (c+1)
if c == 1:
    for i in range(n):
        if X[i]:
            print((0))
        else:
            print((dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1))
else:
    b = x % (c-1)
    for i in range(n):
        if X[i]:
            print((dp[(b - pow(2, n-i-1, c-1)) % (c-1)] + 1))
        else:
            print((dp[(a + pow(2, n-i-1, c+1)) % (c+1)] + 1))
# Original solution
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(eval(input()))
    X = readline()
    bit_count = X.count('1')
    X_int = int(X, 2)


    for i in range(N):
        # ビットの反転
        bit_count_n = bit_count
        X_rest = 0
        if X[i] == '0':
            bit_count_n += 1
            X_rest = X_int + pow(2, N - 1 - i)
        else:
            bit_count_n -= 1
            X_rest = X_int - pow(2, N - 1 - i)

        if X_rest == 0:
            print((0))
        else:
            popcount_X = X_rest % bit_count_n
            counter = 1
            while popcount_X != 0:
                popcount_X %= bin(popcount_X).count('1')
                counter += 1
            print(counter)






# Optimized solution
def popcount(n):
    bit_count = bin(n).count('1')
    n = n % bit_count 
    return n

if __name__ == "__main__":
    import sys 

    readline = sys.stdin.readline 

    N = int(eval(input()))
    X = readline()
    bit_count = X.count('1')
    mod1 = int(X, 2) % (bit_count + 1)
    mod2 = int(X, 2) % (bit_count - 1) if (bit_count - 1) != 0 else 0

    for i in range(N):
        if X[i] == '0':
            X_rest = (mod1 + pow(2, N - 1 - i, bit_count + 1)) % (bit_count + 1)
        else:
            if bit_count - 1 != 0:
                X_rest = (mod2 - pow(2, N - 1 - i, bit_count - 1)) % (bit_count - 1)
            else:
                print((0))
                continue

        counter = 1
        while X_rest != 0:
            X_rest = popcount(X_rest)
            counter += 1
        print(counter)
# Original solution
N = int(eval(input()))
X = input().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = nX % MOD1
if MOD2 != 0:
    nXm = nX % MOD2

delta = 2**(N-1)
pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print((f(k) + 1))
    else:
        if MOD2 == 0:
            print((0))
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print((f(k) + 1))
    delta //= 2

# Optimized solution
import sys

N = int(sys.stdin.readline().strip())
X = sys.stdin.readline().strip()

def popcount(n):
    cnt = 0
    while n > 0:
        cnt += n & 1
        n //= 2
    return cnt

def f(n):
    cnt = 0
    while n != 0:
        n = n % popcount(n)
        cnt += 1
    return cnt

#nX = int(X, 2)
pcnt = X.count('1')
MOD1 = pcnt + 1
MOD2 = pcnt - 1

nXp = 0
nXm = 0

pow1 = [1] * N
pow2 = [0] * N
for i in range(1, N):
    pow1[i] = (pow1[i-1] * 2) % MOD1
if MOD2 != 0:
    pow2[0] = 1
    for i in range(1, N):
        pow2[i] = (pow2[i-1] * 2) % MOD2

for i in range(N):
    if X[i] == '1':
        nXp += pow1[N-1-i]
nXp %= MOD1

if MOD2 != 0:
    for i in range(N):
        if X[i] == '1':
            nXm += pow2[N-1-i]

    nXm %= MOD2
    

for i in range(0, N):
    if X[i] == '0':
        k = (nXp + pow1[N-1-i]) % MOD1
        print((f(k) + 1))
    else:
        if MOD2 == 0:
            print((0))
        else:
            k = (nXm - pow2[N-1-i]) % MOD2
            print((f(k) + 1))
# Original solution
import sys
from collections import defaultdict

sys.setrecursionlimit(300000)

memp = {}
def popcount(n):
    if n == 0:
        return 0

    global memp
    if n not in memp:
        memp[n] = (n & 1) + popcount(n >> 1)
    return memp[n]

memf = {}
def f(x):
    if x == 0:
        return 0

    global memf
    if x not in memf:
        memf[x] = f(x % popcount(x)) + 1
    return memf[x]

n = int(eval(input()))
x = input().rstrip()

ans = []
for j in range(n):
    i = n - 1 - j
    a = str(1 - int(x[i]))
    b = x[:i] + a + x[i+1:]
    ans.append(f(int(b, 2)))
for j in range(n):
    i = n - 1 - j
    print((ans[i]))

# Optimized solution
import sys
from collections import defaultdict
from collections import Counter

sys.setrecursionlimit(300000)

memp = {}
def popcount(n):
    if n == 0:
        return 0

    global memp
    if n not in memp:
        memp[n] = (n & 1) + popcount(n >> 1)
    return memp[n]

memf = {}
def f(x):
    if x == 0:
        return 0

    global memf
    if x not in memf:
        memf[x] = f(x % popcount(x)) + 1
    return memf[x]

n = int(eval(input()))
x = input().rstrip()

init = Counter(x)['1']
for i in range(n):
    if x[i] == '1':
        pc = init - 1
    else:
        pc = init + 1
    nn = int(x[:i] + str(1 - int(x[i])) + x[i+1:], 2)
    if nn == 0:
        print((0))
        continue

    nn = nn % pc
    ans = 1
    while nn != 0:
        nn = nn % popcount(nn)
        ans += 1
    print(ans)
# Original solution
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bit1 = bitm - pow(2,N-1-i)
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
    else:
      bit1 = bitp + pow(2,N-1-i)
      bl1 = bl+1
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')


# Optimized solution
def solve():
  N = int(input())
  X = input()
  bl = X.count('1')
  bitp = 0
  for i in range(N):
    bitp += int(X[i])*pow(2,N-1-i,bl+1)
    bitp %= bl+1
  bitm = 0
  if bl>1:
    for i in range(N):
      bitm += int(X[i])*pow(2,N-1-i,bl-1)
      bitm %= bl-1
  
  ans = [0]*N
  dp = [0]*(N+1)
  for i in range(1,N+1):
    dp[i] = dp[i%(bin(i).count('1'))]+1
  for i in range(N):
    if X[i]=='1':
      bl1 = bl-1
      if bl1==0:
        ans[i] = 0
        continue
      bit1 = bitm - pow(2,N-1-i,bl1)
    else:
      bl1 = bl+1
      bit1 = bitp + pow(2,N-1-i,bl1)
    ans[i] = dp[bit1%bl1]+1
  return ans
print(*solve(),sep='\n')
# Original solution
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + (1 << (n - i - 1))) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - (1 << (n - i - 1))) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")


# Optimized solution
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")
# Original solution
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


ret = [rec(x) for x in range(2 * 10**5 + 1)]


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(ret[x] + 1)

print(*ans, sep="\n")


# Optimized solution
from functools import lru_cache


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


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    else:
        return rec(n % popcnt(n)) + 1


n = int(input())
arr = input()

ALL_ARR = int(arr, 2)

cnt = popcnt(int(arr, 2))
init_big = ALL_ARR % (cnt + 1)
if cnt == 1:
    init_small = 0
else:
    init_small = ALL_ARR % (cnt - 1)


li = [0] * n
for i in range(n):
    if arr[i] == "0":
        li[i] = (init_big + pow(2, n - i - 1, cnt + 1)) % (cnt + 1)
    elif ALL_ARR - (1 << (n - i - 1)) == 0 or cnt - 1 == 0:
        li[i] = "flg"
    else:
        li[i] = (init_small - pow(2, n - i - 1, cnt - 1)) % (cnt - 1)


ans = []

for x in li:
    if x == "flg":
        ans.append(0)
    else:
        ans.append(rec(x) + 1)

print(*ans, sep="\n")
# Original solution
def main():
    import sys
    input=sys.stdin.readline
    n=int(eval(input()))
    x=input().rstrip()
    p=x.count("1")
    minus=0
    plus=0
    numlst=[0]*n
    for i in range(n):
        number=2**i
        numlst[-i-1]=number
        if x[-i-1]=="1":
            plus+=number
            plus%=(p+1)
            if p!=1:
                minus+=number
                minus%=(p-1)

    def popcnt(x):
        cnt=str(bin(x)).count("1")
        x%=cnt
        return x

    for i in range(n):
        if x[i]=="0":
            amari=(plus+numlst[i]%(p+1))%(p+1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)
        else:
            if p==1:
                print((0))
                continue
            amari=(minus-numlst[i]%(p-1))%(p-1)
            ans=1
            while amari>=1:
                amari=popcnt(amari)
                ans+=1
            print(ans)

if __name__ == "__main__":
    main()

# Optimized solution
import sys
input=sys.stdin.readline
n=int(eval(input()))
x=input().rstrip()
x10=int(x,2)
pcx=x.count("1")

plus=x10%(pcx+1)
if pcx>=2:
    minus=x10%(pcx-1)

def popcnt(x):
    cnt=1
    while x>=1:
        x%=(bin(x).count("1"))
        cnt+=1
    return cnt

for i in range(n):
    if x[i]=="0":
        amari=(plus+pow(2,n-i-1,pcx+1))%(pcx+1)
        print((popcnt(amari)))
    else:
        if pcx==1:
            print((0))
        else:
            amari=(minus-pow(2,n-i-1,pcx-1))%(pcx-1)
            print((popcnt(amari)))
# Original solution
import sys
readline = sys.stdin.readline

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    if count1 > 1:
      pat = (X0mod1to0 - val % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val *= 2

print(*ans, sep = "\n")


# Optimized solution
import sys
readline = sys.stdin.readline

N = int(readline())
X = readline().rstrip()

X0 = int(X, 2)
count1 = X.count("1")

X0mod0to1 = X0 % (count1 + 1) # 0->1に変化した際の、X0を割った余り
if count1 > 1:
  X0mod1to0 = X0 % (count1 - 1) # 1->0に変化した際の、X0を割った余り
else:
  X0mod1to0 = 0

from collections import defaultdict
dp = defaultdict(int)
dp[0] = 0
def f(x): # 愚直にf(x)を求める式
  if x in dp:
    return dp[x]
  pc = bin(x).count("1")
  val = f(x % pc) + 1
  dp[x] = val
  return val
  
val0to1 = 1
val1to0 = 1
ans = [-1] * N

for i in range(N - 1, -1, -1): # 下の桁から順に、f(Xi)の値を求める
  if X[i] == "0": # 0を1に変える場合
    pat = (X0mod0to1 + val0to1 % (count1 + 1)) % (count1 + 1)
    ans[i] = f(pat) + 1
  elif X[i] == "1": # 1を0に変える場合
    if count1 > 1:
      pat = (X0mod1to0 - val1to0 % (count1 - 1)) % (count1 - 1)
      ans[i] = f(pat) + 1
    else:
      ans[i] = 0
  val0to1 = val0to1 * 2 % (count1 + 1)
  if count1 != 1:
    val1to0 = val1to0 * 2 % (count1 - 1)

print(*ans, sep = "\n")
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
import sys
import re

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = list(map(int,input().split(" ")))
r = re.compile("[0-9]")
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif r.match(char) is not None:
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)

# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
import sys

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = list(map(int,input().split(" ")))
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif char.isnumeric():
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)
# Original solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
import sys

def check_out_of_map(pos,H,W):
    H = len(Map)
    W = len(Map[0])

    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = list(map(int,input().split(" ")))
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif char.isnumeric():
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)

# Optimized solution
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import heapq
import sys

def check_out_of_map(pos,H,W):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= H or pos[1] >= W:
        return False
    return True

def bfs(s,g,Map,H,W):
    queue = []
    queue.append(s)
    dist = [[-1 for i in range(W)] for j in range(H)]
    direct = [(1,0),(-1,0),(0,1),(0,-1)]
    count = 0
    dist[s[0]][s[1]] = 0

    while queue != []:
        q = queue.pop(0)
        if q == g:
            return dist[q[0]][q[1]]
        for i in range(4):
            nextPos = (q[0]+direct[i][0],q[1]+direct[i][1])
            if check_out_of_map(nextPos,H,W) and Map[nextPos[0]][nextPos[1]] != "X":
                if dist[nextPos[0]][nextPos[1]] == -1:
                    dist[nextPos[0]][nextPos[1]] = dist[q[0]][q[1]] + 1
                    queue.append(nextPos)

H,W,N = list(map(int,input().split(" ")))
cheese_queue = []
Map = []
for i in range(H):
    count = 0
    line = []
    while True:
        char = sys.stdin.read(1)
        if char == "S":
            s = (i,count)
        elif char.isnumeric():
            heapq.heappush(cheese_queue,(int(char),(i,count)))
        elif char == "\n":
            break
        line.append(char)
        count += 1
    Map.append(line)
count = 0
while cheese_queue != []:
    q = heapq.heappop(cheese_queue)
    count += bfs(s,q[1],Map,H,W)
    s = q[1]
print(count)
# Original solution
def f(s):
    s=list(map(int,s.split(':')))
    return (s[0]*60+s[1])*60+s[2]
a=86401
while 1:
    t=[0]*a
    n=int(eval(input()))
    if n==0:break
    for _ in range(n):
        b,c=input().split()
        t[f(b)]+=1;t[f(c)]-=1
    d=0
    for i in range(1,a):
        t[i]+=t[i-1]
        d=max(d,t[i])
    print(d)

# Optimized solution
def f(s):
    return (s[0]*60+s[1])*60+s[2]
a=86400
while 1:
    t=[0]*a
    n=int(eval(input()))
    if n==0:break
    for _ in range(n):
        b,c = [list(map(int,x.split(':'))) for x in input().split()]
        t[f(b)]+=1;t[f(c)]-=1
    d=0
    for i in range(1,a):
        t[i]+=t[i-1]
        if d<t[i]:d=t[i]
    print(d)
# Original solution
m=24*60*60
while True:
	n=int(eval(input()))
	if n==0:break
	dp=[0]*(m+1)
	for _ in range(n):
		a,d=input().split()
		a,b,c=list(map(int,a.split(':')));
		d,e,f=list(map(int,d.split(':')));
		dp[a*3600+b*60+c]+=1
		dp[d*3600+e*60+f]-=1
	for i in range(m):
		dp[i+1]+=dp[i]
	print((max(dp)))

# Optimized solution
m=24*60*60
while True:
	n=int(input())
	if n==0:break
	dp=[0]*(m+1)
	for _ in range(n):
		a,d=input().split()
		a,b,c=list(map(int,a.split(':')));
		d,e,f=list(map(int,d.split(':')));
		dp[a*3600+b*60+c]+=1
		dp[d*3600+e*60+f]-=1
	for i in range(m):
		dp[i+1]+=dp[i]
	print((max(dp)))