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

#AIsing2020 d

import sys,math,collections,itertools,copy
input = sys.stdin.readline


def popcount(n):
    cou1 = 0
    while n>0:
        cou1+=n%2
        n = n//2
    return cou1

def count(nc):
    co = 0
    while nc >0:
        cou1 = popcount(nc)
        nc = nc%cou1
        co +=1
    return co

N = int(input())
X = int('0b'+input().rstrip(),2)

for i in range(N,0,-1):
    a = X
    if a>>(i-1) & 1:
        a -= 2**(i-1)
    else:
        a += 2**(i-1)
    co = count(a)
    print(co)
    


### FIXED CODE ###

#AIsing2020 d

def f(n):
        cnt = 0
        while n:
            cnt+= 1
            n = n%bin(n).count('1')
        return cnt

def main():
    N = int(input())
    X = input()
    X10 = int(X,2)
    X10_num1 = X.count('1')
    X10_pulse = X10%(X10_num1+1)
    X10_ninus = X10%(X10_num1-1) if X10_num1 >1 else 0


    for i in range(N,0,-1):
        j = N-i
        if (X[j] == '1') and X10_num1 >1:
            mod = X10_num1-1
            amari = (X10_ninus - pow(2,i-1,mod))%(mod) 
        elif (X[j] == '1') and X10_num1 ==1:
            print(0)
            continue
        else:
            mod = X10_num1+1
            amari = (X10_pulse + pow(2,i-1,mod))%(mod)

        print(1+f(amari))


main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        if not able[u]:
            continue
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')


### FIXED CODE ###

import sys

sys.setrecursionlimit(200000)


def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)


def close(v, i):
    j = int(s[v] == 'B')
    for u in links[v][i].copy():
        if not able[u]:
            continue
        links[u][j].discard(v)
        if not links[u][j]:
            able[u] = False
            close(u, j ^ 1)


n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)

for v in range(n):
    if able[v]:
        continue
    close(v, bool(links[v][1]))

print('Yes' if any(able) else 'No')
### BUGGY CODE ###

n = int(input())
s_dic = {}
for i in range(n):
    s = input()
    if s not in s_dic:
        s_dic[s] = 1
    else:
        s_dic[s] += 1
max_s_list = [s[0] for s in s_dic.items() if s[1] == max(s_dic.values())]
max_s_list.sort()
for s in max_s_list:
    print(s)


### FIXED CODE ###

from collections import Counter

n = int(input())
s_list = []

for i in range(n):
    s_list.append(input())

s_list.sort()
c = Counter(s_list)
l = c.most_common()    
count = l[0][1]
l.sort()
for i in l:
    if count == i[1]:
        print(i[0])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [sum(c[i:b + i]) for i in range(a - b + 1)]
e = 0
g = d.index(max(d))
for i in range(b):
	f = sum(range(1, c[g + i] + 1))
	e += f / c[g + i]
print(e)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = list(map(int, input().split()))
d = [(i + 1) / 2 for i in c]
e = sum(d[:b])
f = e
for i in range(a - b):
	f -= d[i]
	f += d[i + b]
	if f > e:
		e = f
print(e)
### BUGGY CODE ###

C,D = [int(e) for e in input().split()]

if C <= D:
    m = D
    n = C
else:
    m = C
    n = D

while  n != 0 :
    a = m%n
    m = n
    n = a

J = []
for i in range(1, int(m**0.5)+1):
    if m % i == 0:
        J.append(i)
        if i != m//i:
            J.append(m//i)


J.sort()

N = int(len(J))
M = [1]
I = []

for i in range(1,N):
    for p in range(1,J[i]+1):
        if J[i]%p == 0:
            I.extend([J[i]])
    if int(len(I)) == 2:
        M.extend([J[i]])
    I = []


M = int(len(M))

print(M)

### FIXED CODE ###

C,D = [int(e) for e in input().split()]

if C <= D:
    m = D
    n = C
else:
    m = C
    n = D

while  n != 0 :
    a = m%n
    m = n
    n = a

J = []

for i in range(1,int(m**0.5)+1):
    if m % i == 0:
        J.append(i)
        if i != m//i:
            J.append(m//i)


J.sort()

N = int(len(J))
M = [1]
I = []

for i in range(1,N):
    for p in range(1,int(J[i]**0.5)+1):
        if J[i]%p == 0:
            I.extend([J[i]])
            if int(len(I)) >=2:
                break
    if int(len(I)) == 1:
        M.extend([J[i]])
    I = []


M = int(len(M))

print(M)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 10**9 + 10

for i in range(n):
    west = s[:i].count('W')
    east = s[i:].count('E')
    if west + east < ans:
        ans = west + east

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = [s[1:].count('E')]

for i in range(1, n):
    num = ans[i - 1]
    if s[i - 1] == 'E':
        num -= 1
    if s[i] == 'W':
        num += 1
    ans.append(num)

print(min(ans))
### BUGGY CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
d=[0]*n
for i in range(n-1):
    d[i]=sorted(a)[i+1]-sorted(a)[i]
d[-1]=k+sorted(a)[0]-sorted(a)[n-1]
print(k-max(d))

### FIXED CODE ###

k,n=map(int,input().split())
a=list(map(int,input().split()))
d=0
for i in range(n-1):
    d=max(a[i+1]-a[i],d)
d=max(k+a[0]-a[n-1],d)
print(k-d)
### BUGGY CODE ###

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

A_sum = [0]
for i in range(N):
    A_sum.append(A[i]+A_sum[i])

B_sum = [0]
for i in range(M):
    B_sum.append(B[i]+B_sum[i])

max_count = 0
for i in range(N+1):
    j = M
    if A_sum[i] > K:
        break

    while B_sum[j] + A_sum[i] > K:
        j -= 1
    max_count = max(max_count, i + j)
print(max_count)

### FIXED CODE ###

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

A_sum = [0]
for i in range(N):
    A_sum.append(A[i]+A_sum[i])

B_sum = [0]
for i in range(M):
    B_sum.append(B[i]+B_sum[i])

max_count = 0
j = M
for i in range(N+1):
    if A_sum[i] > K:
        break

    while B_sum[j] + A_sum[i] > K:
        j -= 1
    max_count = max(max_count, i + j)
print(max_count)
### BUGGY CODE ###

MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = 2**(n-1), 0 if n <= 1 else 2**(n-2)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * (2 ** n % MOD) % MOD)


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
c = list(map(int, input().split()))
c.sort(reverse=True)
cnt = 0
a, b = pow(2, n-1, MOD), 0 if n <= 1 else pow(2, n-2, MOD)
for i, x in enumerate(c):
    cnt += (a + b*i) * x
    cnt %= MOD

print(cnt * pow(2, n, MOD) % MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

cs = [[0] * (w + 1) for _ in range(h + 1)]
for i in range(h):
    for j in range(w):
        cs[i + 1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

# print(*cs, sep='\n')
# print()

ans = h + w
for bit in range(1 << (h - 1)):
    border = [0]
    cand = 0
    for i in range(h):
        if (bit >> i) & 1 == 1:
            border.append(i + 1)
            cand += 1
    border.append(h)
    cand0 = cand
    j0 = 0
    cut = []
    j = 1
    while j <= w:
        # for j in range(1, w + 1):
        for i in range(len(border) - 1):
            # print(
            #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
            #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
            if cs[border[i + 1]][j] - cs[border[i + 1]][j0] - cs[
                    border[i]][j] + cs[border[i]][j0] > k:
                cand += 1
                j0 = j - 1
                j -= 1
                cut.append(j - 1)
                # print(border[i + 1], j, cs[border[i + 1]][j])
                break
        j += 1

    # print(border, cand0, cand, cut)
    ans = min(ans, cand)
print(ans)


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    h, w, k = map(int, input().split())
    s = [input() for _ in range(h)]

    cs = [[0] * (w + 1) for _ in range(h + 1)]
    for i in range(h):
        for j in range(w):
            cs[i +
               1][j +
                  1] = cs[i][j + 1] + cs[i + 1][j] - cs[i][j] + int(s[i][j])

    # print(*cs, sep='\n')
    # print()

    ans = h + w
    for bit in range(1 << (h - 1)):
        border = [0]
        cand = 0
        for i in range(h):
            if (bit >> i) & 1:
                border.append(i + 1)
                cand += 1
        border.append(h)
        if cand >= ans:
            continue
        j0 = 0
        j = 1
        while j <= w:
            # for j in range(1, w + 1):
            for i, bi in enumerate(border[:-1]):
                # print(
                #     j0, j, border[i], border[i + 1], cs[border[i + 1]][j] -
                #     cs[border[i + 1]][j0] - cs[border[i]][j] + cs[border[i]][j0])
                if cs[border[i + 1]][j] - cs[border[
                        i + 1]][j0] - cs[bi][j] + cs[bi][j0] > k:
                    cand += 1
                    j0 = j - 1
                    j -= 1
                    # print(border[i + 1], j, cs[border[i + 1]][j])
                    break
            j += 1
            if cand >= ans:
                break

        # print(border, cand0, cand, cut)
        ans = min(ans, cand)
    print(ans)


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

# -*- coding: utf-8 -*-

import math

r,g,b,n = map(int,input().split())

ans = 0
for i in range(math.ceil(n / r)+1):
    for j in range(math.ceil(n / g)+1):
        if (n - r * i - g * j) % b == 0 and (n - r * i - g * j) >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import math

r,g,b,n = map(int,input().split())

ans = 0
for i in range(math.ceil(n / r)+1):
    for j in range(math.ceil(n / g)+1):
        if (n - r * i - g * j) % b == 0 and (n - r * i - g * j) >= 0:
            ans += 1

print(ans)
### BUGGY CODE ###

import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    s =input()
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue
            for k in range(j+1, n):
                if s[i] == s[k] or s[j] == s[k]:
                    continue
                if j-i != k-j:
                    cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def main():
    n = I()
    s = list(input())
    r = s.count('R')
    g = s.count('G')
    b = s.count('B')
    cnt = r*g*b
    for i in range(n):
        for j in range(i+1, n):
            k = 2*j - i
            if k >= n:
                break
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                cnt -= 1
    print(cnt)

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

from sys import exit

A, B = map(int, input().split())

ans = 0

for i in range(A, B + 1):
    ans = ans ^ i

print(ans)


### FIXED CODE ###

from sys import exit

A, B = map(int, input().split())


def get_xor(x):
    if x % 4 == 0:
        return x
    elif x % 4 == 1:
        return 1
    elif x % 4 == 2:
        return 1 + x
    elif x % 4 == 3:
        return 0


ans = get_xor(A - 1) ^ get_xor(B)

print(ans)
### BUGGY CODE ###

k=int(input())
import fractions
x=0
c=0
d=0
for i in range(1,k+1):
  for j in range(i,k+1):
    for k in range(j,k+1):
      d=fractions.gcd(i,j)
      c=fractions.gcd(d,k)
      if i!=j and j!=k:
        x+=6*c
      elif i==j==k:
        x+=c
      else:
        x+=3*c
print(x)

### FIXED CODE ###

k=int(input())
import math
x=0
c=0
d=0
for i in range(1,k+1):
  for j in range(i,k+1):
    for k in range(j,k+1):
      d=math.gcd(i,j)
      c=math.gcd(d,k)
      if i!=j and j!=k:
        x+=6*c
      elif i==j==k:
        x+=c
      else:
        x+=3*c
print(x)
### BUGGY CODE ###

from collections import deque

def reachable(es, source):
	ret = {source}
	Q = [source]
	while Q:
		cur = Q.pop()
		for nxt in es[cur]:
			if nxt not in ret:
				Q.append(nxt)
				ret.add(nxt)
	return ret

def SPFA(G:list, source=0):
	V = len(G)
	d = [float("inf")]*V
	inQ = [False]*V
	cnt = [0]*V
	d[source] = 0
	cnt[source] = 1
	Q = deque([source])
	_sum = 0
	_len = 1
	while Q:
		f = Q.popleft()
		inQ[f] = False
		_sum -= d[f]
		_len -= 1
		for t,c in G[f]:
			dist = d[f] + c
			if dist < d[t]:
				d[t] = dist
				if not inQ[t]:
					inQ[t] = True
					cnt[t] += 1
					if dist*_len < _sum:
						Q.appendleft(t)
					else:
						Q.append(t)
					_sum += dist
					_len += 1
				if cnt[t] > V:
					#negative cycle
					return None
	return d[-1]
	
def main():
	N,M,P,*L=map(int,open(0).read().split())
	fwd = [[] for _ in range(N)]
	bwd = [[] for _ in range(N)]
	tmp = [[] for _ in range(N)]
	G = [[] for _ in range(N)]
	for a,b,c in zip(*[iter(L)]*3):
		fwd[a-1].append(b-1)
		bwd[b-1].append(a-1)
		tmp[a-1].append((b-1,P-c))
	judge = reachable(fwd,0) & reachable(bwd,N-1)
	for a,es in enumerate(tmp):
		if a not in judge:
			continue
		for b,c in es:
			if b in judge:
				G[a].append((b,c))
	ans = SPFA(G)
	if ans==None:
		print(-1)
	else:
		print(max(0,-ans))

if __name__=="__main__":
	main()


### FIXED CODE ###

n,m,p = map(int,input().split())
graph = [[] for _ in range(n)]
INF = float("inf")
dist = [INF]*n
dist[0] = 0

for _ in range(m):
	f,t,c = map(int,input().split())
	graph[f-1].append((t-1,p-c))
#print(graph)

for _ in range(n):
	update = False
	for f,e in enumerate(graph):
		for t,c in e:
			if dist[f] != INF and dist[t] > dist[f] + c:
				dist[t] = dist[f] + c
				update = True
	if not update:
		break
else:
	prev = dist[-1]
	for _ in range(n):
		update = False
		for f,e in enumerate(graph):
			for t,c in e:
				if dist[f] != INF and dist[t] > dist[f] + c:
					dist[t] = dist[f] + c
					update = True
		if not update:
			break
	if dist[-1] != prev:
		print(-1)
		exit()
#print(dist)

print(max(0,dist[-1]*(-1)))
### BUGGY CODE ###

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

list_size = 2000

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % p)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % p) * f_r_list[r - 1]) % p 

ans = [0 for _ in range(p)]
for i, x in enumerate(a):
	if x == 1:
		ans[0] += 1
		ans[0] %= p
		for j in range(p):
			ans[j] -= pow(i, p-1-j, p)
			ans[j] %= p

print(*ans)

### FIXED CODE ###

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

list_size = p-1

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % p)

f_r_list[-1] = pow(f_list[-1], p - 2, p)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % p)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % p) * f_r_list[r - 1]) % p 

pows = [[1] for x in range(p)]
for i in range(p):
	for _ in range(p-1):
		pows[i].append((pows[i][-1] * i) % p)

ans = [0 for _ in range(p)]
for i, x in enumerate(a):
	if x == 0:
		continue
	ans[0] += 1
	ans[0] %= p
	for j in range(p):
		ans[j] -= pows[(p-i)%p][p-1-j] * comb(p-1, j)
		ans[j] %= p

print(*ans)
### BUGGY CODE ###

from heapq import heappop, heappush 
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()

    def toId(x, y, v): return (x*(w+2)+y)*4 + v

    def modCeil(x): return x + (-x)%k

    def dijkstra():
        inf = 1e18

        dp = [inf]*(h+2)*(w+2)*4
        dp[toId(xs, ys, 0)] = 0

        que = [(0, toId(xs, ys, 0))]
        dx = [-1, 0, 1, 0]
        dy = [0, 1, 0, -1]
        while que:
            cost, Id = heappop(que)
            x = Id//4//(w+2)
            y = Id//4%(w+2)
            v = Id%4

            if cost > dp[Id]:
                continue
            
            for nv in range(4):
                nId = toId(x, y, nv)
                if dp[nId] > cost:
                    dp[nId] = modCeil(cost)
                    heappush(que, (dp[nId], nId))
            
            nx, ny = x+dx[v], y+dy[v]
            nId = toId(nx, ny, v)
            if field[nx][ny]:
                if dp[nId] > cost + 1:
                    dp[nId] = cost + 1
                    heappush(que, (dp[nId], nId))

        ans = inf
        for v in range(4):
            ans = min(ans, dp[toId(xg, yg, v)])
        if ans == inf:       
            return -1
        return modCeil(ans)//k

    h, w, k= map(int, input().split())
    xs, ys, xg, yg = map(int, input().split())
    field = [[False]*(w+2)]
    for _ in range(h):
        s = [False]
        s += [True if i == '.' else False for i in input()]
        s += [False]
        field.append(s)
    field.append([False]*(w+2))
    ans = dijkstra()
    print(ans)




if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    
    h, w, k = map(int, input().split())
    xs, ys, xg, yg = map(lambda x: int(x)-1, input().split())
    field = [input() for _ in range(h)]

    inf = 1e7

    dist = [[inf]*w for _ in range(h)]
    dist[xs][ys] = 0
    que = deque([(xs, ys)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    while que:
        x, y = que.popleft()
        for i in range(4):
            nx, ny = x, y
            for _ in range(k):
                nx += dx[i]
                ny += dy[i]
                if nx < 0 or nx >= h or ny < 0 or ny >= w: break
                if field[nx][ny] == '@' or dist[nx][ny] <= dist[x][y]: break
                if dist[nx][ny] > dist[x][y] + 1:
                    dist[nx][ny] = dist[x][y] + 1
                    que.append((nx, ny))
        
    if dist[xg][yg] == inf:
        print(-1)
    else:
        print(dist[xg][yg])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

if k % 2 == 0:
    check = k // 2
else:
    check = k

cnt = 0
for a in range(check, n+1, check):
    for b in range(check, n+1, check):
        for c in range(check, n+1, check):
            if (a + b) % k or (b + c) % k or (c + a) % k:
                continue
            else:
                cnt += 1

print(cnt)

### FIXED CODE ###

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

if k % 2 == 0:
    even = n // k
    odd = n // (k // 2) - even
    print(odd ** 3 + even ** 3)
else:
    print((n // k) ** 3)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())
prize_list = []
for prize in s:
    if prize in prize_list:
        continue
    else:
        prize_list.append(prize)
print(len(prize_list))

### FIXED CODE ###

n = int(input())
s = set()
for i in range(n):
    s.add(input())
print(len(s))
### BUGGY CODE ###

from collections import deque
INF = 1e9
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(sy, sx, gy, gx):
    if wall[sy][sx]=="#":
        return 0
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    m = 0
    while len(que) > 0:
        y, x = que.popleft()

        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0 <= ny and ny < h and 0 <= nx and nx < w and wall[ny][nx] != "#" and d[ny][nx] <0:
                que.append((ny, nx))
                d[ny][nx] = d[y][x]+1
    return d[gy][gx]


h, w = map(int, input().split())
wall = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                d = [[-1]*w for _ in range(h)]
                a = bfs(i, j, k, l)
                ans = max(ans, a)
print(ans)

### FIXED CODE ###

from collections import deque
INF = 1e9
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def bfs(sy, sx):
    if wall[sy][sx]=="#":
        return 0
    que = deque()
    que.append((sy, sx))
    d[sy][sx] = 0
    m = 0
    while len(que) > 0:
        y, x = que.popleft()

        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if 0 <= ny and ny < h and 0 <= nx and nx < w and wall[ny][nx] != "#" and d[ny][nx] == INF:
                que.append((ny, nx))
                d[ny][nx] = d[y][x]+1
                m = max(d[ny][nx],m)
    return m


h, w = map(int, input().split())
wall = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        d = [[INF]*w for _ in range(h)]
        a = bfs(i, j)
        ans = max(ans, a)
print(ans)
### BUGGY CODE ###

K = int(input())

from fractions import gcd

ans = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            if i == j and j == k and k == i:
                ans += i
            elif i == j or j == k or k == i:
                x = gcd(i, j)
                ans += gcd(x, k) * 3
            else:
                x = gcd(i, j)
                ans += gcd(x, k) * 6
print(ans)

### FIXED CODE ###

K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            if i == j and j == k and k == i:
                ans += i
            elif i == j or j == k or k == i:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 3
            else:
                x = math.gcd(i, j)
                ans += math.gcd(x, k) * 6
print(ans)
### BUGGY CODE ###

t = input()
for i in range(len(t)):
    x = t[i]
    if x == '?':
        t = t[:i] + 'D' + t[i+1:]
print(t)



### FIXED CODE ###

t = input()
t = t.replace('?','D')
print(t)
### BUGGY CODE ###

from sys import stdin

K = int(stdin.readline())

if K < 50000:
    count = 0
    for _ in range(1, 3234566667):
        i = str(_)
        L = len(i)
        for j in range(1, L):
            if abs(ord(i[j]) - ord(i[j - 1])) > 1:
                break
        else:
            count += 1
            if count == K:
                print(_)
                quit()
else:
    count = 100001
    for _ in range(1, 3234566668)[::-1]:
        i = str(_)
        L = len(i)
        for j in range(1, L):
            if abs(ord(i[j]) - ord(i[j - 1])) > 1:
                break
        else:
            count -= 1
            if count == K:
                print(_)
                quit()


### FIXED CODE ###

from sys import stdin
from collections import deque

K = int(stdin.readline())

deque = deque()
for i in range(1, 10):
    deque.append(i)

for i in range(K - 1):
    s = deque.popleft()
    for j in range(-1, 2):
        add = (s % 10) + j
        if 0 <= add <= 9:
            deque.append(s * 10 + add)

print(deque.popleft())