AtCoder Beginner Contest 077 - Small Multiple

Find the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

-----Constraints-----
 - 2 \leq K \leq 10^5
 - K is an integer.

-----Input-----
Input is given from Standard Input in the following format:
K

-----Output-----
Print the smallest possible sum of the digits in the decimal notation of a positive multiple of K.

-----Sample Input-----
6

-----Sample Output-----
3

12=6×2 yields the smallest sum.

Difficulty: MEDIUM_HARD

Starter code:

Solutions:
import collections
k = int(input())
lst = [k + 1] * k
q = collections.deque([1])
lst[1] = 1
while q:
	a = q.pop()
	if lst[a * 10 % k] > lst[a]:
		lst[a * 10 % k] = lst[a]
		q.append(a * 10 % k)
	if lst[(a + 1) % k] >= lst[a] + 1:
		lst[(a + 1) % k] = lst[a] + 1
		q.appendleft((a + 1) % k)
print(lst[0])


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from heapq import heappush, heappop
INF = float('inf')

def main():
	K = int(input())
	graph = defaultdict(list)
	for i in range(K):
		graph[i].append((1, (i + 1) % K))
		graph[i].append((0, i * 10 % K))
	cost = [INF] * K
	cost[1] = 1
	que = deque()
	que.appendleft(1)
	while len(que) != 0:
		now = que.popleft()
		for (c, node) in graph[now]:
			new_cost = cost[now] + c
			if new_cost < cost[node]:
				cost[node] = new_cost
				if c == 0:
					que.appendleft(node)
				else:
					que.append(node)
	print(cost[0])
main()


from collections import deque
k = int(input())
t = [1] * k
q = deque()
q.append((1, 1))
while q:
	(p, r) = q.popleft()
	if p == 0:
		print(r)
		break
	if t[p]:
		t[p] = 0
		q.appendleft((p * 10 % k, r))
		q.append(((p + 1) % k, r + 1))


import collections
K = int(input())
q = collections.deque([(1, 0)])
v = {1}
while len(q) > 0:
	(c, p) = q.popleft()
	v.add(c)
	if c == 0:
		break
	(n1, n10) = ((c + 1) % K, c * 10 % K)
	if not n1 in v:
		q.append((n1, p + 1))
	if not n10 in v:
		q.appendleft((n10, p))
print(p + 1)


from collections import deque
K = int(input())
deq = deque([(1, 1)])
history = set()
while True:
	to = deq.popleft()
	if to[0] == 0:
		print(to[1])
		break
	elif to[0] not in history:
		history.add(to[0])
		deq.appendleft((to[0] * 10 % K, to[1]))
		deq.append((to[0] + 1, to[1] + 1))


from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import *
import sys, random, itertools, math
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline
sqrt = math.sqrt

def LI():
	return list(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def LI_():
	return list(map(lambda x: int(x) - 1, input().split()))

def II():
	return int(input())

def I():
	return int(sys.stdin.readline())

def IF():
	return float(input())

def LS():
	return list(map(list, input().split()))

def S():
	return list(input().rstrip())

def IR(n):
	return [II() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def FR(n):
	return [IF() for _ in range(n)]

def LFR(n):
	return [LI() for _ in range(n)]

def LIR_(n):
	return [LI_() for _ in range(n)]

def SR(n):
	return [S() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

def A():
	a = input()
	b = input()
	if a[2] == b[0] and a[1] == b[1] and (a[0] == b[2]):
		print('YES')
	else:
		print('NO')
	return

def B():
	n = I()
	n = int(math.sqrt(n))
	print(n ** 2)
	return

def C():
	n = I()
	a = LI()
	a.sort()
	b = LI()
	b.sort()
	c = LI()
	c.sort()
	ans = 0
	for i in b:
		x = bisect_left(a, i)
		x = x * (n - bisect_right(c, i))
		ans += x
	print(ans)
	return

def D():
	k = II()
	dp = [inf] * k
	q = deque()
	q.append(1)
	dp[1] = 1
	while q:
		i = q.pop()
		if dp[i * 10 % k] > dp[i]:
			dp[i * 10 % k] = dp[i]
			q.appendleft(i * 10 % k)
		if dp[(i + 1) % k] > dp[i] + 1:
			dp[(i + 1) % k] = dp[i] + 1
			q.append((i + 1) % k)
	print(dp[0])
	return
D()


import queue

def bfs01(s: int, t: int, V: int, graph: list) -> int:
	INF = float('inf')
	q = queue.deque([])
	qc = 0
	l = [INF] * V
	q.append(s)
	qc += 1
	l[s] = 0
	while qc > 0:
		u = q.popleft()
		qc -= 1
		for (v, c) in graph[u]:
			if l[u] + c < l[v]:
				l[v] = l[u] + c
				qc += 1
				if c == 0:
					q.appendleft(v)
				else:
					q.append(v)
	return l[t]

def small_multiple(K: int) -> int:
	graph = []
	for k in range(K):
		graph.append([])
		v1 = k + 1 if k + 1 < K else 0
		v10 = k * 10 % K
		graph[k].append((v1, 1))
		if v10 != k:
			graph[k].append((v10, 0))
	return bfs01(1, 0, K, graph) + 1
K = int(input())
ans = small_multiple(K)
print(ans)


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from heapq import heappop, heappush
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float('inf')
(YES, Yes, yes, NO, No, no) = ('YES', 'Yes', 'yes', 'NO', 'No', 'no')
(dy4, dx4) = ([0, 1, 0, -1], [1, 0, -1, 0])

def inside(y, x, H, W):
	return 0 <= y < H and 0 <= x < W

def ceil(a, b):
	return (a + b - 1) // b

def main():
	K = int(input())
	dp = [INF] * K
	dp[1] = 1
	heap = []
	heappush(heap, (1, 1))
	while len(heap) != 0:
		(k, p) = heappop(heap)
		if dp[(p + 1) % K] > dp[p] + 1:
			dp[(p + 1) % K] = dp[p] + 1
			heappush(heap, (dp[p] + 1, (p + 1) % K))
		if dp[p * 10 % K] > dp[p]:
			dp[p * 10 % K] = dp[p]
			heappush(heap, (dp[p], p * 10 % K))
		if dp[0] != INF:
			break
	print(dp[0])

def __starting_point():
	main()
__starting_point()


import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop, heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10 ** 9 + 7
inf = float('inf')

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))
k = I()
graph = [[] for _ in range(k)]
for i in range(k):
	graph[i].append([(i + 1) % k, 1])
	graph[i].append([10 * i % k, 0])

def dijkstra(x):
	d = [inf] * k
	d[x] = 1
	visited = {x}
	h = [(0, x)]
	while h:
		u = heappop(h)[1]
		visited.add(u)
		for (node, cost) in graph[u]:
			if node not in visited and d[node] > d[u] + cost:
				d[node] = d[u] + cost
				heappush(h, (d[u] + cost, node))
	return d
print(dijkstra(1)[0])


from collections import deque
K = int(input())
while K % 2 == 0:
	K = K // 2
while K % 5 == 0:
	K = K // 5
if K == 1:
	print('1')
else:
	visited = [-1 for i in range(K)]
	queue = deque([])
	st = 1
	while True:
		visited[st] = 1
		queue.append(st)
		st = 10 * st % K
		if st == 1:
			break
	while queue:
		a = queue.popleft()
		if visited[0] != -1:
			break
		if visited[(a + 1) % K] == -1:
			st = (a + 1) % K
			while True:
				visited[st] = visited[a] + 1
				queue.append(st)
				st = 10 * st % K
				if st == (a + 1) % K:
					break
			if visited[0] != -1:
				break
	print(visited[0])


from collections import deque
K = int(input())
d = [-1] * K
Q = [0] * (K + 1)
p = 0
q = 0
d[1] = 1
Q[q] = 1
q += 1
while q - p > 0:
	sp = p
	ep = q
	while ep - sp > 0:
		for i in range(sp, ep):
			x = Q[i]
			y = 10 * x % K
			if d[y] < 0:
				d[y] = d[x]
				Q[q] = y
				q += 1
		(sp, ep) = (ep, q)
	for i in range(p, q):
		x = Q[i]
		p += 1
		y = (x + 1) % K
		if d[y] < 0:
			d[y] = d[x] + 1
			Q[q] = y
			q += 1
print(d[0])


from collections import deque
K = int(input())
G = [None] * K
for i in range(K):
	G[i] = ((10 * i % K, 0), ((i + 1) % K, 1))
s = 1
dist = [10 ** 9] * K
S = deque([s])
T = deque()
dist[s] = 0
d = 0
while S:
	while S:
		v = S.popleft()
		for (w, c) in G[v]:
			if d + c < dist[w]:
				dist[w] = d + c
				if c:
					T.append(w)
				else:
					S.append(w)
	(S, T) = (T, S)
	d += 1
print(dist[0] + 1)


from collections import deque
K = int(input())
d = [1000000 for x in range(K + 1)]
d[1] = 1

def bfs(K):
	q = deque()
	q.append(1)
	while q:
		nx = q.popleft()
		if d[nx * 10 % K] > d[nx]:
			d[nx * 10 % K] = d[nx]
			q.appendleft(nx * 10 % K)
		if d[(nx + 1) % K] > d[nx] + 1:
			d[(nx + 1) % K] = d[nx] + 1
			q.append((nx + 1) % K)
	return d[0]
print(bfs(K))


def D_SmallMultiple(K):
	import collections
	q = collections.deque()
	q.append(1)
	dp = [float('Inf') for _ in range(K)]
	dp[1] = 0
	while q:
		u = q.popleft()
		if dp[u * 10 % K] > dp[u]:
			dp[u * 10 % K] = dp[u]
			q.appendleft(u * 10 % K)
		if dp[(u + 1) % K] > dp[u] + 1:
			dp[(u + 1) % K] = dp[u] + 1
			q.append((u + 1) % K)
	return dp[0] + 1
K = int(input())
print(D_SmallMultiple(K))


import sys
input = sys.stdin.readline
import math
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache
MOD = 10 ** 9 + 7
INF = float('inf')
AZ = 'abcdefghijklmnopqrstuvwxyz'

def I():
	return int(input().strip())

def S():
	return input().strip()

def IL():
	return list(map(int, input().split()))

def SL():
	return list(map(str, input().split()))

def ILs(n):
	return list((int(input()) for _ in range(n)))

def SLs(n):
	return list((input().strip() for _ in range(n)))

def ILL(n):
	return [list(map(int, input().split())) for _ in range(n)]

def SLL(n):
	return [list(map(str, input().split())) for _ in range(n)]

def P(arg):
	print(arg)
	return

def Y():
	print('Yes')
	return

def N():
	print('No')
	return

def E():
	exit()

def PE(arg):
	print(arg)
	exit()

def YE():
	print('Yes')
	exit()

def NE():
	print('No')
	exit()

def DD(arg):
	return defaultdict(arg)

def inv(n):
	return pow(n, MOD - 2, MOD)
kaijo_memo = []

def kaijo(n):
	if len(kaijo_memo) > n:
		return kaijo_memo[n]
	if len(kaijo_memo) == 0:
		kaijo_memo.append(1)
	while len(kaijo_memo) <= n:
		kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
	return kaijo_memo[n]
gyaku_kaijo_memo = []

def gyaku_kaijo(n):
	if len(gyaku_kaijo_memo) > n:
		return gyaku_kaijo_memo[n]
	if len(gyaku_kaijo_memo) == 0:
		gyaku_kaijo_memo.append(1)
	while len(gyaku_kaijo_memo) <= n:
		gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo), MOD - 2, MOD) % MOD)
	return gyaku_kaijo_memo[n]

def nCr(n, r):
	if n == r:
		return 1
	if n < r or r < 0:
		return 0
	ret = 1
	ret = ret * kaijo(n) % MOD
	ret = ret * gyaku_kaijo(r) % MOD
	ret = ret * gyaku_kaijo(n - r) % MOD
	return ret

def factorization(n):
	arr = []
	temp = n
	for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
		if temp % i == 0:
			cnt = 0
			while temp % i == 0:
				cnt += 1
				temp //= i
			arr.append([i, cnt])
	if temp != 1:
		arr.append([temp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr

def make_divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	return divisors

def make_primes(N):
	max = int(math.sqrt(N))
	seachList = [i for i in range(2, N + 1)]
	primeNum = []
	while seachList[0] <= max:
		primeNum.append(seachList[0])
		tmp = seachList[0]
		seachList = [i for i in seachList if i % tmp != 0]
	primeNum.extend(seachList)
	return primeNum

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

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

def count_bit(n):
	count = 0
	while n:
		n &= n - 1
		count += 1
	return count

def base_10_to_n(X, n):
	if X // n:
		return base_10_to_n(X // n, n) + [X % n]
	return [X % n]

def base_n_to_10(X, n):
	return sum((int(str(X)[-i - 1]) * n ** i for i in range(len(str(X)))))

def base_10_to_n_without_0(X, n):
	X -= 1
	if X // n:
		return base_10_to_n_without_0(X // n, n) + [X % n]
	return [X % n]

def int_log(n, a):
	count = 0
	while n >= a:
		n //= a
		count += 1
	return count
N = I()
graph = [[] for i in range(N)]
for i in range(N):
	graph[i].append((1, (i + 1) % N))
for i in range(N):
	graph[i].append((0, i * 10 % N))

def bfs(graph, start):
	N = len(graph)
	d = [INF] * N
	d[start] = 0
	q = deque([start])
	while q:
		u = q.popleft()
		for (c, v) in graph[u]:
			if d[v] <= d[u] + c:
				continue
			d[v] = d[u] + c
			if c:
				q.append(v)
			else:
				q.appendleft(v)
	return d
d = bfs(graph, 1)
print(d[0] + 1)


from collections import deque
k = int(input())
q = deque()
q.append(1)
d = [float('inf')] * k
d[1] = 1
while q:
	n = q.popleft()
	(l, r) = (n * 10 % k, (n + 1) % k)
	if d[l] > d[n]:
		d[l] = d[n]
		q.appendleft(l)
	if d[r] > d[n] + 1:
		d[r] = d[n] + 1
		q.append(r)
print(d[0])


import sys
sys.setrecursionlimit(1000000)

def input():
	return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from math import *
from heapq import *

def dijkstra(s, edges, INF=10 ** 20):
	dist = [INF for _ in range(len(edges))]
	(dist[s], h) = (0, [])
	heappush(h, (0, s))
	while len(h):
		(dv, v) = heappop(h)
		if dv > dist[v]:
			continue
		for (u, cost) in edges[v]:
			if dv + cost < dist[u]:
				dist[u] = dv + cost
				heappush(h, (dist[u], u))
	return dist
K = int(input())
es = [[] for i in range(K)]
for i in range(1, K):
	k = i * 10
	for j in range(10):
		es[i].append([(k + j) % K, j])
print(dijkstra(1, es)[0] + 1)


from heapq import heappush, heappop

def dijkstra(graph: list, n: int, v_s: int, INF: int=float('inf')) -> list:
	dist = [INF] * n
	dist[v_s] = 0
	heap = [(0, v_s)]
	while heap:
		(dist2v, v_from) = heappop(heap)
		if dist[v_from] < dist2v:
			continue
		for (cost, v_to) in graph[v_from]:
			dist_cand = dist2v + cost
			if dist_cand < dist[v_to]:
				dist[v_to] = dist_cand
				heappush(heap, (dist[v_to], v_to))
	return dist
k = int(input())
graph = [[] for _ in range(k)]
for i in range(1, k):
	graph[i].append((1, (i + 1) % k))
	graph[i].append((0, 10 * i % k))
dist = dijkstra(graph, k, 1)
ans = dist[0] + 1
print(ans)


from collections import deque
K = int(input())
visited = [False] * K
Q = deque([(1, 1)])
while True:
	(s, v) = Q.popleft()
	if v == 0:
		print(s)
		quit()
	if visited[v]:
		continue
	visited[v] = True
	Q.appendleft((s, 10 * v % K))
	Q.append((s + 1, (v + 1) % K))


def bfs_01(v, mod):
	q = deque()
	q.append(v)
	visited = [False] * mod
	cur = 0
	while cur == 0:
		(s, x) = q.popleft()
		if visited[x]:
			continue
		visited[x] = True
		if x == 0:
			cur = s
			return cur
		q.appendleft((s, 10 * x % mod))
		q.append((s + 1, (x + 1) % mod))

def examD():
	K = I()
	ans = bfs_01((1, 1), K)
	print(ans)
import sys, copy, bisect, itertools
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

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

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
inf = float('inf')
examD()


from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

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

def I():
	return int(sys.stdin.readline())

def LS():
	return list(map(list, sys.stdin.readline().split()))

def S():
	return list(sys.stdin.readline())[:-1]

def IR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = I()
	return l

def LIR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = LI()
	return l

def SR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = S()
	return l

def LSR(n):
	l = [None for i in range(n)]
	for i in range(n):
		l[i] = SR()
	return l
mod = 1000000007

def A():
	s = S()
	t = S()
	if s + t == t[::-1] + s[::-1]:
		print('YES')
	else:
		print('NO')

def B():
	n = I()
	for i in range(int(n ** 0.5) + 2)[::-1]:
		if i * i <= n:
			print(i * i)
			quit()

def C():
	n = I()
	a = LI()
	b = LI()
	c = LI()
	q = [0 for i in range(n)]
	ans = 0
	a.sort()
	b.sort()
	c.sort()
	for i in range(n):
		j = bisect.bisect_left(a, b[i])
		q[i] = j
	for i in range(n - 1):
		q[i + 1] += q[i]
	q.insert(0, 0)
	for i in range(n):
		j = bisect.bisect_left(b, c[i])
		ans += q[j]
	print(ans)

def D():

	def dijkstra():
		d = [float('inf') for i in range(k)]
		q = [[0, 1]]
		d[1] = 0
		while q:
			(dx, x) = heappop(q)
			for (y, dy) in v[x]:
				if d[y] > dx + dy:
					d[y] = dx + dy
					heappush(q, [d[y], y])
		print(d[0] + 1)
	k = I()
	if k == 1:
		print(1)
		quit()
	v = [[] for i in range(k)]
	for i in range(1, k):
		v[i].append([(i + 1) % k, 1])
		v[i].append([i * 10 % k, 0])
	dijkstra()

def E():
	return

def F():
	return

def G():
	return

def H():
	return
D()


import sys
sys.setrecursionlimit(10 ** 9)

def int1(x):
	return int(x) - 1

def II():
	return int(input())

def MI():
	return map(int, input().split())

def MI1():
	return map(int1, input().split())

def LI():
	return list(map(int, input().split()))

def LI1():
	return list(map(int1, input().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SMI():
	return input().split()

def SLI():
	return list(input())

def printlist(lst, k=' '):
	print(k.join(list(map(str, lst))))
INF = float('inf')
from collections import deque

def solve():
	K = II()
	q = deque([(1, 1)])
	used = [0 for _ in range(K)]
	while len(q) > 0:
		(v, cost) = q.popleft()
		if v == 0:
			print(cost)
			return
		if used[v]:
			continue
		used[v] = 1
		q.appendleft((v * 10 % K, cost))
		q.append(((v + 1) % K, cost + 1))
solve()


K = int(input())
D = [K * 10] * K
D[1] = 1
import heapq
Q = [(1, 1)]
while Q:
	(c, x) = heapq.heappop(Q)
	if D[x * 10 % K] > c:
		D[x * 10 % K] = c
		heapq.heappush(Q, (c, x * 10 % K))
	if D[(x + 1) % K] > c + 1:
		D[(x + 1) % K] = c + 1
		heapq.heappush(Q, (c + 1, (x + 1) % K))
print(D[0])


K = int(input())
G = [[] for _ in range(K)]
for i in range(K):
	G[i].append((1, (i + 1) % K))
	G[i].append((0, i * 10 % K))
from collections import deque
que = deque([1])
dist = [-1] * K
dist[1] = 0
import heapq
inf = 10 ** 10

def dijkstra(s, n, G):
	dist = [inf] * n
	edges = []
	dist[s] = 0
	for e in G[s]:
		heapq.heappush(edges, e)
	while edges:
		(cost, v) = heapq.heappop(edges)
		if dist[v] != inf:
			continue
		dist[v] = cost
		for (c, nv) in G[v]:
			if dist[nv] == inf:
				heapq.heappush(edges, (cost + c, nv))
	return dist
dist = dijkstra(1, K, G)
print(dist[0] + 1)


from collections import deque
K = int(input())
E = [[((i + 1) % K, 1)] for i in range(K)]
for i in range(1, K):
	E[i].append((i * 10 % K, 0))
Q = deque([(1, 1)])
reached = set()
while 1:
	(tmp_node, tmp_cost) = Q.popleft()
	if tmp_node == 0:
		ans = tmp_cost
		break
	if tmp_node in reached:
		continue
	reached.add(tmp_node)
	for (nxt, dist) in E[tmp_node]:
		if dist == 0:
			Q.appendleft((nxt, tmp_cost))
		else:
			Q.append((nxt, tmp_cost + 1))
print(ans)


import sys
from collections import deque
readline = sys.stdin.readline
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int, readline().split()))

def solve():
	k = ni()
	q = deque()
	q.append(1)
	dist = [k] * k
	dist[1] = 1
	while q:
		v = q.popleft()
		if dist[(v + 1) % k] > dist[v] + 1:
			dist[(v + 1) % k] = dist[v] + 1
			q.append((v + 1) % k)
		if dist[v * 10 % k] > dist[v]:
			dist[v * 10 % k] = dist[v]
			q.appendleft(v * 10 % k)
	print(dist[0])
	return
solve()


from collections import deque
K = int(input())
reached = [0 for i in range(K)]
reached[1] = 1
dist = [0 for i in range(K)]
q = deque([])
q.append(1)
while len(q) > 0:
	r = q.popleft()
	v = (r + 1) % K
	reached[r] = 1
	if reached[v] == 0:
		q.append(v)
		dist[v] = dist[r] + 1
	v = r * 10 % K
	if reached[v] == 0:
		q.appendleft(v)
		dist[v] = dist[r]
	if reached[0] == 1:
		break
print(dist[0] + 1)


import itertools
from scipy.sparse import coo_matrix, lil_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford, floyd_warshall
N = int(input())
rows = []
cols = []
weights = []
for i in range(N):
	rows.append(i)
	cols.append((i + 1) % N)
	weights.append(1)
for i in range(N):
	if i - 10 * i % N == -1:
		weights[i] = 0
	elif i == N - 1 and i - 10 * i % N == 1:
		weights[i] = 0
	else:
		rows.append(i)
		cols.append(10 * i % N)
		weights.append(0)
graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)
print(int(d1[0] + 1.5))


from collections import deque
K = int(input())
q = deque()
q.append((1, 1, 1))
used = set()
while True:
	(x, y, k) = q.popleft()
	if k % K == 0:
		print(x)
		break
	if (x, 0, k * 10 % K) in used:
		continue
	else:
		used.add((x, 0, k * 10 % K))
	q.appendleft((x, 0, k * 10 % K))
	if (y + 1) % 10 == 0:
		q.appendleft((x, 0, k + 1))
	else:
		q.append((x + 1, y + 1, k + 1))


from collections import deque

def solve(K):
	checked = [99999999999] * (K + 1)
	queue = deque()
	queue.append((1, 1))
	checked[1] = 1
	while queue:
		(x, n) = queue.popleft()
		if x == 0:
			return n
		_ = x * 10 % K
		if n < checked[_]:
			queue.appendleft((_, n))
			checked[_] = n
		_ = (x + 1) % K
		if n + 1 < checked[_]:
			queue.append((_, n + 1))
			checked[_] = n + 1
	return None
K = int(input())
print(solve(K))


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

def main():
	k = int(readline())
	v = list(range(k))
	inf = float('inf')
	dist = [inf] * k
	visited = [0] * k
	stack = deque([1])
	dist[1] = 0
	while stack:
		v = stack.pop()
		if not visited[v]:
			nv0 = 10 * v % k
			nv1 = (v + 1) % k
			if dist[nv0] > dist[v]:
				dist[nv0] = dist[v]
				stack.append(nv0)
			if dist[nv1] > dist[v] + 1:
				dist[nv1] = dist[v] + 1
				stack.appendleft(nv1)
			visited[v] = 1
	print(dist[0] + 1)

def __starting_point():
	main()
__starting_point()


from collections import deque
K = int(input())
G = [[] for i in range(K)]
for i in range(K):
	G[i].append(((i + 1) % K, 1))
	G[i].append((10 * i % K, 0))
dist = [float('inf')] * K
dist[1] = 1
que = deque()
que.append(1)
while que:
	n = que.pop()
	for (v, c) in G[n]:
		if dist[v] > dist[n] + c:
			dist[v] = dist[n] + c
			if c == 0:
				que.append(v)
			else:
				que.appendleft(v)
print(dist[0])


from collections import *
from heapq import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

def DIJKSTRA(point, d, n):
	cost = {node: float('inf') for node in range(n)}
	Q = []
	cost[point] = 0
	heappush(Q, (point, cost[point]))
	while Q:
		(prefnd, tmpC) = heappop(Q)
		if cost[prefnd] < tmpC:
			continue
		for (node, c) in d[prefnd]:
			altC = c + tmpC
			if cost[node] > altC:
				cost[node] = altC
				heappush(Q, (node, altC))
	return cost

def main():
	k = int(input())
	d = defaultdict(list)
	for i in range(k - 1):
		d[i].append([i + 1, 1])
	d[k - 1].append([0, 1])
	for i in range(k):
		d[i].append([i * 10 % k, 0])
	print(DIJKSTRA(1, d, k)[0] + 1)
main()


from heapq import heappush, heappop
k = int(input())
heap = [(1, 1)]
dist = [float('inf')] * k
while heap:
	(cost, cur) = heappop(heap)
	if dist[cur] <= cost:
		continue
	dist[cur] = cost
	nxt = (cur + 1) % k
	heappush(heap, (cost + 1, nxt))
	nxt = cur * 10 % k
	heappush(heap, (cost, nxt))
print(dist[0])


import sys
from collections import deque

def input():
	return sys.stdin.readline().strip()

def main():
	K = int(input())
	repn = [[] for _ in range(K)]
	for i in range(K):
		repn[i].append(10 ** 6 + (i + 1) % K)
		repn[i].append(i * 10 % K)
	q = deque([])
	cost = [0] * K
	cost[1] = 1
	for val in repn[1]:
		(type, toward) = (val // 10 ** 6, val % 10 ** 6)
		if type == 0:
			q.appendleft(1 * 10 ** 6 + toward)
		else:
			q.append(10 ** 12 + 1 * 10 ** 6 + toward)
	while q:
		x = q.popleft()
		(type, x) = (x // 10 ** 12, x % 10 ** 12)
		(pre, now) = (x // 10 ** 6, x % 10 ** 6)
		if cost[now] != 0:
			continue
		cost[now] = cost[pre] + type
		for val in repn[now]:
			(type, toward) = (val // 10 ** 6, val % 10 ** 6)
			if type == 0:
				q.appendleft(now * 10 ** 6 + toward)
			else:
				q.append(10 ** 12 + now * 10 ** 6 + toward)
	print(cost[0])
main()


import heapq
K = int(input())
dist = [10 ** 15 for i in range(K)]
dist[1] = 1
q = []
heapq.heappush(q, (0, 1))
while len(q) != 0:
	(prc, src) = heapq.heappop(q)
	if dist[src] < prc:
		continue
	if dist[(src + 1) % K] > dist[src] + 1:
		dist[(src + 1) % K] = dist[src] + 1
		heapq.heappush(q, (dist[(src + 1) % K], (src + 1) % K))
	if dist[10 * src % K] > dist[src]:
		dist[10 * src % K] = dist[src]
		heapq.heappush(q, (dist[src * 10 % K], src * 10 % K))
print(dist[0])


from collections import deque
k = int(input())
que = deque()
que.append((1, 1))
dist = [float('inf')] * k
while que:
	(cost, cur) = que.popleft()
	if dist[cur] <= cost:
		continue
	dist[cur] = cost
	nxt = (cur + 1) % k
	que.append((cost + 1, nxt))
	nxt = cur * 10 % k
	que.appendleft((cost, nxt))
print(dist[0])


from collections import deque

def bfs01(g, start):
	n = len(g)
	res = [float('inf')] * n
	res[start] = 0
	pending = n - 1
	q = deque([(0, start)])
	while q and pending:
		(dv, v) = q.popleft()
		if res[v] < dv:
			continue
		pending -= 1
		for (to, cost) in g[v]:
			if dv + cost < res[to]:
				res[to] = dv + cost
				if cost:
					q.append((res[to], to))
				else:
					q.appendleft((res[to], to))
	return res
import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
k = int(input())
g = [[] for _ in range(k)]
for i in range(k):
	g[i].append(((i + 1) % k, 1))
	g[i].append((10 * i % k, 0))
res = bfs01(g, 1)
print(res[0] + 1)


from scipy.sparse.csgraph import dijkstra, shortest_path
from scipy.sparse import csr_matrix
K = int(input())

class Graph(object):

	def __init__(self, K):
		self.K = K
		self.weights = {}

	def add_edge(self, node1, node2, weight):
		if (node1, node2) in self.weights:
			self.weights[node1, node2] = min(self.weights[node1, node2], weight)
		else:
			self.weights[node1, node2] = weight

	def get_csr_matrix(self):
		(n1, n2, w) = ([], [], [])
		for ((node1, node2), weight) in self.weights.items():
			n1.append(node1)
			n2.append(node2)
			w.append(weight)
		return csr_matrix((w, (n1, n2)), shape=(self.K, self.K))
g = Graph(K)
for i in range(K - 1):
	g.add_edge(i, i + 1, 1)
	g.add_edge(i, i * 10 % K, 10 ** (-16))
g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, (K - 1) * 10 % K, 10 ** (-16))
d = dijkstra(g.get_csr_matrix(), directed=True, indices=1)
print(int(d[0]) + 1)


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()

def resolve():
	k = int(input())
	dist = [INF] * k
	dist[1] = 1
	queue = [1]
	for v in queue:
		tmp = [v]
		for v in tmp:
			if dist[10 * v % k] > dist[v]:
				dist[10 * v % k] = dist[v]
				tmp.append(10 * v % k)
			if dist[(v + 1) % k] > dist[v] + 1:
				dist[(v + 1) % k] = dist[v] + 1
				queue.append((v + 1) % k)
	print(dist[0])
resolve()


import sys
from collections import deque

def main():
	input = sys.stdin.readline
	N = int(input())
	q = deque([[1, 1]])
	d = {1: 1}
	while q:
		(n, c) = q.popleft()
		a = n * 10 % N
		if a not in d or d[a] > c:
			d[a] = c
			q.appendleft([a, c])
		b = (n + 1) % N
		if b not in d or d[b] > c + 1:
			d[b] = c + 1
			q.append([b, c + 1])
	print(d[0])
main()


import collections

def ans(n):
	dist = [10 ** 5] * n
	dist[1] = 1
	d = collections.deque()
	d.append(1)
	while not d.count == 0:
		u = d.popleft()
		if u == 0:
			return dist[u]
		if dist[u] < dist[u * 10 % n]:
			dist[u * 10 % n] = dist[u]
			d.appendleft(u * 10 % n)
		if dist[u] < dist[(u + 1) % n]:
			dist[(u + 1) % n] = dist[u] + 1
			d.append((u + 1) % n)
n = int(input())
print(ans(n))


K = int(input())
import collections
d = [float('inf')] * K
d[1] = 1
path = [[] for _ in range(K)]
for i in range(K - 1):
	path[i].append((i + 1, 1))
path[-1].append((0, 1))
for i in range(K):
	path[i].append((i * 10 % K, 0))
deque = collections.deque([1])
while deque:
	s = deque.popleft()
	for (e, cost) in path[s]:
		if d[s] + cost < d[e]:
			d[e] = d[s] + cost
			if cost == 0:
				deque.appendleft(e)
			else:
				deque.append(e)
print(d[0])


from collections import deque
import sys
sys.setrecursionlimit(10 ** 6)
k = int(input())
q = deque()
q.append(1)
dp = [10 ** 10] * k
dp[1] = 0
while q:
	u = q.popleft()
	if dp[u * 10 % k] > dp[u]:
		dp[u * 10 % k] = dp[u]
		q.appendleft(u * 10 % k)
	if dp[(u + 1) % k] > dp[u] + 1:
		dp[(u + 1) % k] = dp[u] + 1
		q.append((u + 1) % k)
print(dp[0] + 1)


from collections import deque
q = deque()
K = int(input())
a = q.append
a((1, 1))
m = {}
while len(q):
	(n, s) = q.popleft()
	if n in m:
		continue
	m[n] = s
	q.appendleft((n * 10 % K, s))
	a(((n + 1) % K, s + 1))
print(m[0])


k = int(input())
from collections import deque
d = deque()
d.append((1, 1))
discovered = set()
while True:
	(node, cost) = d.popleft()
	discovered |= {node}
	if node == 0:
		print(cost)
		quit()
	if node * 10 % k not in discovered:
		d.appendleft((node * 10 % k, cost))
	if (node + 1) % k not in discovered:
		d.append((node + 1, cost + 1))


from collections import deque
K = int(input())
V = [0] * K
d = deque([(1, 1)])
while 1:
	(w, v) = d.popleft()
	if v == 0:
		ans = w
		break
	if V[v] == 1:
		continue
	V[v] = 1
	if V[(v + 1) % K] == 0:
		d.append((w + 1, (v + 1) % K))
	if V[v * 10 % K] == 0:
		d.appendleft((w, v * 10 % K))
print(ans)


from collections import deque
k = int(input())
v = list(range(k))
stack = deque([1])
inf = float('inf')
visited = [0] * k
dist = [inf] * k
dist[1] = 0
while stack:
	v = stack.pop()
	if not visited[v]:
		nv0 = 10 * v % k
		nv1 = (v + 1) % k
		if dist[nv0] > dist[v]:
			dist[nv0] = dist[v]
			stack.append(nv0)
		if dist[nv1] > 1 + dist[v]:
			stack.appendleft(nv1)
			dist[nv1] = dist[v] + 1
		visited[v] = 1
print(dist[0] + 1)


import heapq
from collections import deque
K = int(input())
G = [[] for i in range(K)]
for n in range(K):
	G[n].append([(n + 1) % K, 1])
	G[n].append([10 * n % K, 0])

def dijkstra(x):
	d = [float('inf')] * K
	d[x] = 0
	visited = {x}
	hq = [(0, x)]
	while hq:
		u = heapq.heappop(hq)[1]
		visited.add(u)
		for (node, cost) in G[u]:
			if node not in visited and d[node] > d[u] + cost:
				d[node] = d[u] + cost
				heapq.heappush(hq, (d[u] + cost, node))
	return d
print(dijkstra(1)[0] + 1)


from collections import deque
K = int(input())
INF = 10 ** 9 + 7
A = [INF] * K
q = deque()
q.append(1)
A[1] = 1
while q:
	x = q.popleft()
	if A[x * 10 % K] > A[x]:
		A[x * 10 % K] = A[x]
		q.appendleft(x * 10 % K)
	if A[(x + 1) % K] > A[x] + 1:
		A[(x + 1) % K] = A[x] + 1
		q.append((x + 1) % K)
print(A[0])


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
k = int(input())
g = [[] for i in range(k)]
for i in range(k):
	g[i].append(((i + 1) % k, 1))
	if i:
		g[i].append((10 * i % k, 0))
dq = deque([1])
res = [float('inf')] * k
res[1] = 1
while dq:
	v = dq.popleft()
	if v == 0:
		break
	for (t, cost) in g[v]:
		if res[t] <= res[v] + cost:
			continue
		res[t] = res[v] + cost
		if cost:
			dq.append(t)
		else:
			dq.appendleft(t)
print(res[0])


K = int(input())
import heapq

def dijkstra(adj, n, start):
	dj = [10 ** 6] * (n + 1)
	dj[start] = 0
	q = []
	heapq.heappush(q, (0, start))
	while q:
		(fc, fn) = heapq.heappop(q)
		if dj[fn] < fc:
			continue
		for (tn, lc) in adj[fn]:
			if dj[tn] > dj[fn] + lc:
				dj[tn] = dj[fn] + lc
				heapq.heappush(q, (dj[tn], tn))
	return dj
adj = {}
for i in range(K):
	t = adj.setdefault(i, [])
	t.append(((i + 1) % K, 1))
	t.append((i * 10 % K, 0))
costs = dijkstra(adj, K - 1, 1)
print(costs[0] + 1)


from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
INF = float('inf')

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

def I():
	return int(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return sys.stdin.readline().strip()

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]

def SRL(n):
	return [list(S()) for i in range(n)]

def MSRL(n):
	return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007
k = I()
cost = [INF] * k
cost[1] = 1
que = deque([1])
while que:
	cur = que.popleft()
	nxt = cur * 10 % k
	if cost[cur] < cost[nxt]:
		cost[nxt] = cost[cur]
		que.appendleft(nxt)
	nxt = (cur + 1) % k
	if cost[cur] + 1 < cost[nxt]:
		cost[nxt] = cost[cur] + 1
		que.append(nxt)
print(cost[0])


from heapq import heappop, heappush

def dijkstra(s, n, edge):
	inf = 10 ** 20
	ans = [inf] * n
	ans[s] = 0
	h = [[0, s]]
	while h:
		(c, v) = heappop(h)
		if ans[v] < c:
			continue
		for (u, t) in edge[v]:
			if c + t < ans[u]:
				ans[u] = c + t
				heappush(h, [c + t, u])
	return ans
k = int(input())
edge = [[] for _ in range(k)]
for i in range(1, k):
	edge[i].append((i * 10 % k, 0))
	edge[i].append(((i + 1) % k, 1))
ans = dijkstra(1, k, edge)
print(ans[0] + 1)


from collections import deque

def BFS01(d, K):
	d[1] = 1
	q = deque([1])
	while q:
		n = q.popleft()
		(l, r) = map(lambda x: x % K, [n * 10, n + 1])
		if d[l] > d[n]:
			d[l] = d[n]
			q.appendleft(l)
		if d[r] > d[n] + 1:
			d[r] = d[n] + 1
			q.append(r)
	return d[0]
K = int(input())
d = [float('inf')] * K
print(BFS01(d, K))


from collections import deque
K = int(input())
L = {i: 10 ** 6 for i in range(K)}
L[1] = 1
biq = deque()
biq.append(1)
while len(biq) > 0:
	i = biq.popleft()
	if i == 0:
		break
	j = i * 10 % K
	if L[j] > L[i]:
		L[j] = L[i]
		biq.appendleft(j)
	k = 0 if i == K - 1 else i + 1
	if L[k] > L[i]:
		L[k] = L[i] + 1
		biq.append(k)
print(L[0])


from collections import defaultdict
from heapq import heappop, heappush
K = int(input())

class Graph(object):

	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, src, dst, weight=1):
		self.graph[src].append((dst, weight))

	def get_nodes(self):
		return self.graph.keys()

class Dijkstra(object):

	def __init__(self, graph, start):
		g = graph.graph
		self.dist = defaultdict(lambda : float('inf'))
		self.dist[start] = 0
		self.prev = defaultdict(lambda : None)
		Q = []
		heappush(Q, (self.dist[start], start))
		while Q:
			(dist_u, u) = heappop(Q)
			if self.dist[u] < dist_u:
				continue
			for (v, weight) in g[u]:
				alt = dist_u + weight
				if self.dist[v] > alt:
					self.dist[v] = alt
					self.prev[v] = u
					heappush(Q, (alt, v))

	def shortest_distance(self, goal):
		return self.dist[goal]

	def shortest_path(self, goal):
		path = []
		node = goal
		while node is not None:
			path.append(node)
			node = self.prev[node]
		return path[::-1]
g = Graph()
for i in range(K - 1):
	g.add_edge(i, i + 1, 1)
	g.add_edge(i, i * 10 % K, 0)
g.add_edge(K - 1, 0, 1)
g.add_edge(K - 1, (K - 1) * 10 % K, 0)
d = Dijkstra(g, 1)
print(d.shortest_distance(0) + 1)


K = int(input())
G = [((10 * i % K, 0), ((i + 1) % K, 1)) for i in range(K)]
s = 1
dist = [10 ** 9] * K
S = [s]
T = []
dist[s] = 0
d = 0
while S:
	while S:
		v = S.pop()
		for (w, c) in G[v]:
			if d + c < dist[w]:
				dist[w] = d + c
				if c:
					T.append(w)
				else:
					S.append(w)
	(S, T) = (T, S)
	d += 1
print(dist[0] + 1)


import sys

def I():
	return int(sys.stdin.readline().rstrip())
K = I()
Graph = [0] * K
for i in range(K):
	if (i + 1) % K != 10 * i % K:
		Graph[i] = [(1, (i + 1) % K), (0, 10 * i % K)]
	else:
		Graph[i] = [(0, 10 * i % K)]
from heapq import heappush, heappop
d = [100] * K
d[1] = 1
q = []
heappush(q, (1, 1))
v = [False] * K
while q:
	(a, n) = heappop(q)
	if v[n]:
		continue
	v[n] = True
	for (da, dn) in Graph[n]:
		if v[dn]:
			continue
		if a + da < d[dn]:
			d[dn] = a + da
			heappush(q, (a + da, dn))
print(d[0])


import sys
from collections import deque
sys.setrecursionlimit(10000)
INF = float('inf')
K = int(input())
distances = [INF for _ in range(K)]
remains = deque()
remains.append((1, 1))
while distances[0] == INF:
	(d, mod_k) = remains.popleft()
	distances[mod_k] = d
	if distances[(mod_k + 1) % K] == INF:
		remains.append((d + 1, (mod_k + 1) % K))
	if distances[mod_k * 10 % K] == INF:
		remains.appendleft((d, mod_k * 10 % K))
print(distances[0])


from collections import deque
K = int(input())
path = [K] * K
q = deque()
path[1] = 0
q.append(1)
while q:
	p = q.popleft()
	p1 = (p + 1) % K
	if path[p1] > path[p] + 1:
		path[p1] = path[p] + 1
		q.append(p1)
	p10 = p * 10 % K
	if path[p10] > path[p]:
		path[p10] = path[p]
		q.appendleft(p10)
print(path[0] + 1)


from collections import deque
k = int(input())
dist = [float('inf') for _ in range(k)]
dist[1] = 1
q = deque()
q.append(1)
while len(q) > 0:
	r = q.popleft()
	s = (r + 1) % k
	if dist[r] + 1 < dist[s]:
		dist[s] = dist[r] + 1
		q.append(s)
	t = r * 10 % k
	if dist[r] < dist[t]:
		dist[t] = dist[r]
		q.appendleft(t)
print(dist[0])


from collections import deque
k = int(input())
visited = [False] * (k + 1)
dist = [0] * (k + 1)
dist[1] = 1
que = deque([(1, 1)])
while len(que) > 0:
	(cost, node) = que.popleft()
	if visited[node]:
		continue
	visited[node] = True
	dist[node] = cost
	if not visited[10 * node % k]:
		que.appendleft((cost, 10 * node % k))
	if not visited[(node + 1) % k]:
		que.append((cost + 1, (node + 1) % k))
print(dist[0])


import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10 ** 9 + 7

def INT_(n):
	return int(n) - 1

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def MI_():
	return map(INT_, input().split())

def LI():
	return list(MI())

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return list(MF())

def LIN(n: int):
	return [input() for _ in range(n)]

def LLIN(n: int):
	return [LI() for _ in range(n)]

def LLIN_(n: int):
	return [LI_() for _ in range(n)]

def LLI():
	return [list(map(int, l.split())) for l in input()]

def I():
	return int(input())

def F():
	return float(input())

def ST():
	return input().replace('\n', '')

def main():
	from collections import deque
	K = I()
	edge = [[] for _ in range(K)]
	for i in range(K):
		edge[i].append(i * 10 % K)
		edge[i].append((i + 1) % K)
	zero_one_deque = deque([(1, 1)])
	node = [inf] * K
	node[1] = 1
	searched = set()
	while zero_one_deque:
		(from_, digit_sum) = zero_one_deque.popleft()
		if from_ in searched:
			continue
		else:
			searched.add(from_)
			node[from_] = digit_sum
		for (i, to) in enumerate(edge[from_]):
			if i == 0:
				zero_one_deque.appendleft((to, node[from_]))
			else:
				zero_one_deque.append((to, node[from_] + 1))
	print(node[0])
main()


from collections import deque
K = int(input())
E = [[i * 10 % K, (i + 1) % K] for i in range(K)]
INF = K * 10
V = [INF] * K
V[1] = 1
q = deque([1])
i = 1
while q:
	i = q.popleft()
	if V[E[i][0]] > V[i]:
		q.appendleft(E[i][0])
		V[E[i][0]] = V[i]
	if V[E[i][1]] > V[i] + 1:
		q.append(E[i][1])
		V[E[i][1]] = V[i] + 1
print(V[0])


import heapq
k = int(input())
graph = [[] for i in range(k)]
for i in range(k):
	if i != k - 1:
		graph[i].append((1, i + 1))
	else:
		graph[i].append((1, 0))
	if i * 10 % k != i:
		graph[i].append((0, i * 10 % k))
que = []
heapq.heappush(que, (0, 1, 1))
dist = [1145141919] * k
dist[1] = 0
ans = 1145141919
while len(que) > 0:
	(d, v, num) = heapq.heappop(que)
	for (cost, place) in graph[v]:
		if place == 0:
			ans = min(ans, num + 1 if cost else num)
		if d + cost < dist[place]:
			dist[place] = d + cost
			heapq.heappush(que, (d + cost, place, num + 1 if cost else num))
print(ans)


import sys
import itertools
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import sys
import itertools
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
K = int(input())
q = deque()
q.append((1, 1))
visited = [False] * K
ans = 0
while True:
	(s, x) = q.popleft()
	if visited[x]:
		continue
	visited[x] = True
	if x == 0:
		ans = s
		break
	q.appendleft((s, 10 * x % K))
	q.append((s + 1, (x + 1) % K))
print(ans)


from collections import deque
K = int(input())
dist = [10 ** 15 for i in range(K)]
dist[1] = 1
q = deque([1])
while len(q) > 0:
	r = q.popleft()
	s = (r + 1) % K
	if dist[r] + 1 < dist[s]:
		dist[s] = dist[r] + 1
		q.append(s)
	t = r * 10 % K
	if dist[r] < dist[t]:
		dist[t] = dist[r]
		q.appendleft(t)
print(dist[0])


from collections import deque
q = deque()
K = int(input())
q += [(1, 1)]
m = {}
while len(q):
	(n, s) = q.pop()
	if not n in m:
		m[n] = s
		q += [(n * 10 % K, s)]
		q.appendleft(((n + 1) % K, s + 1))
print(m[0])


from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

	def v(n):
		return [n * 10 % k, (n + 1) % k]
	k = I()
	d = [float('inf')] * k
	d[1] = 1
	q = deque([1])
	while q:
		x = q.popleft()
		vx = v(x)
		dx = d[x]
		for c in range(2):
			nd = dx + c
			y = vx[c]
			if nd < d[y]:
				d[y] = nd
				if c:
					q.append(y)
				else:
					q.appendleft(y)
	print(d[0])
	return
solve()


from collections import deque
K = int(input())
dist = {1: 1}
deq = deque([1])
while deq:
	v = deq.popleft()
	w = 10 * v % K
	if dist[v] < dist.get(w, 10 ** 9):
		dist[w] = dist[v]
		deq.appendleft(w)
	w = (v + 1) % K
	if dist[v] + 1 < dist.get(w, 10 ** 9):
		dist[w] = dist[v] + 1
		deq.append(w)
print(dist[0])


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def dijkstra(N: int, nodes: list, src: int) -> list:
	from heapq import heappush, heappop
	res = [INF] * N
	que = [1 * N + src]
	res[src] = 1 * N
	while len(que) != 0:
		cur = heappop(que)
		dist = cur // N
		cur %= N
		for (nxt, cost) in nodes[cur]:
			if dist + cost < res[nxt]:
				res[nxt] = dist + cost
				heappush(que, (dist + cost) * N + nxt)
	return res
K = INT()
nodes = [[] for i in range(K)]
for i in range(K):
	nodes[i].append(((i + 1) % K, 1))
	nodes[i].append((i * 10 % K, 0))
res = dijkstra(K, nodes, 1)
print(res[0])


from heapq import heappush, heappop
K = int(input())
queue = [(1, 1)]
dist = [float('inf')] * K
dist[1] = 1
while queue:
	(cost, cur) = heappop(queue)
	if cost + 1 < dist[(cur + 1) % K]:
		dist[(cur + 1) % K] = cost + 1
		heappush(queue, (cost + 1, (cur + 1) % K))
	if cost < dist[cur * 10 % K]:
		dist[cur * 10 % K] = cost
		heappush(queue, (cost, cur * 10 % K))
print(dist[0])


from collections import deque

def solve(K):
	s = 1
	q = deque()
	q.append(s)
	dists = {}
	dists[s] = 1
	while len(q) > 0:
		n = q.pop()
		if n == 0:
			break
		m = n * 10 % K
		if m not in dists:
			dists[m] = dists[n]
			q.append(m)
		elif dists[m] > dists[n]:
			dists[m] = dists[n]
			q.append(m)
		if n % 10 != 9:
			m = (n + 1) % K
			if m not in dists:
				dists[m] = dists[n] + 1
				q.appendleft(m)
			elif dists[m] > dists[n] + 1:
				dists[m] = dists[n] + 1
				q.appendleft(m)
	return dists[0]

def main():
	K = int(input())
	print(solve(K))
main()


import heapq
K = int(input())
visited = [0] * 100001
visited[1] = 1
queue = [(1, 1)]
while queue and queue[0][1] != 0:
	(cost, value) = heapq.heappop(queue)
	cand1 = value * 10 % K
	cand2 = (value + 1) % K
	if not visited[cand1]:
		visited[cand1] = 1
		heapq.heappush(queue, (cost, cand1))
	if not visited[cand2]:
		visited[cand1] = 1
		heapq.heappush(queue, (cost + 1, cand2))
print(queue[0][0])


from collections import deque
k = int(input())
d = [k] * k
e = [[(0, i * 10 % k), (1, (i + 1) % k)] for i in range(k)]
dq = deque()
dq.append((1, 1))
while dq:
	(c, v) = dq.popleft()
	for (v2nv, nv) in e[v]:
		if v2nv == 0:
			if c < d[nv]:
				d[nv] = c
				dq.appendleft((d[nv], nv))
		elif c + 1 < d[nv]:
			d[nv] = c + 1
			dq.append((d[nv], nv))
print(d[0])


from collections import deque
k = int(input())
x = [50 for i in range(k)]
(x[1], q) = (0, deque())
q.append(1)
while q:
	n = q.pop()
	m = n
	while 1:
		m2 = m * 10 % k
		if x[m2] > x[m]:
			(x[m2], m) = (x[m], m2)
			q.append(m)
		else:
			break
	if x[(n + 1) % k] == 50:
		x[(n + 1) % k] = x[n] + 1
		q.appendleft((n + 1) % k)
print(x[0] + 1)


import heapq

def main():
	k = int(input())
	brdict = {}
	for i in range(1, k):
		if i == k - 1:
			if 10 * (k - 1) % k == 0:
				brdict[i] = [(0, 0)]
			else:
				brdict[i] = [(0, 1)]
		else:
			if i != i * 10 % k:
				brdict[i] = [(i * 10 % k, 0)]
			if i * 10 % k != i + 1:
				brdict[i] = brdict.get(i, []) + [(i + 1, 1)]
	start = 1
	cost = [i for i in range(k)]
	cost[0] = k
	fixed = [False] * k
	fixed[start] = True
	akouho = [(1, start)]
	heapq.heapify(akouho)
	while not all(fixed):
		(fcost, fnode) = heapq.heappop(akouho)
		if fnode == 0:
			break
		fixed[fnode] = True
		for br in brdict[fnode]:
			if not fixed[br[0]]:
				if cost[br[0]] > fcost + br[1]:
					cost[br[0]] = fcost + br[1]
					heapq.heappush(akouho, (cost[br[0]], br[0]))
		if akouho == []:
			break
	print(cost[0])

def __starting_point():
	main()
__starting_point()


import heapq
K = int(input())
G = [[((i + 1) % K, 1)] for i in range(K)]
for i in range(K):
	a = i * 10 % K
	G[i].append((a, 0))

def dijkstra(G, s):
	INF = 10 ** 19
	n = len(G)
	d = [INF] * n
	d[s] = 0
	visited = {s}
	que = [(0, s)]
	while que:
		p = heapq.heappop(que)
		v = p[1]
		visited.add(v)
		for (node, cost) in G[v]:
			if node not in visited and d[node] > d[v] + cost:
				d[node] = d[v] + cost
				heapq.heappush(que, (d[node], node))
	return d
d = dijkstra(G, 1)
print(d[0] + 1)


def solve(K):
	checked = [False] * K

	def calc(x):
		while not checked[x]:
			checked[x] = True
			yield x
			x = x * 10 % K
	i = 0
	xs = [0]
	while 1:
		i += 1
		ys = []
		for x in xs:
			for z in calc((x + 1) % K):
				if z == 0:
					return i
				ys.append(z)
		xs = ys
K = int(input())
print(solve(K))


from collections import deque
que = deque()
K = int(input())
que.append((1, 1))
visited = {}
while len(que) != 0:
	(num, step) = que.popleft()
	if num in visited:
		continue
	visited[num] = step
	que.appendleft((num * 10 % K, step))
	que.append(((num + 1) % K, step + 1))
print(visited[0])


import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul
sys.setrecursionlimit(10000)

def read_int():
	return int(input())

def read_int_n():
	return list(map(int, input().split()))

def read_float():
	return float(input())

def read_float_n():
	return list(map(float, input().split()))

def read_str():
	return input()

def read_str_n():
	return list(map(str, input().split()))

def error_print(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.time()
		ret = f(*args, **kwargs)
		e = time.time()
		error_print(e - s, 'sec')
		return ret
	return wrap

@mt
def slv(K):
	g = defaultdict(dict)
	for i in range(1, K + 1):
		g[i % K][(i + 1) % K] = 1
		g[i % K][i * 10 % K] = 0
	q = deque()
	q.append((1, 0))
	vis = {}
	while q:
		(u, cc) = q.popleft()
		if u == 0:
			return cc + 1
		vis[u] = True
		for (v, c) in g[u].items():
			if v in vis:
				continue
			if c == 0:
				q.appendleft((v, cc))
			else:
				q.append((v, cc + c))

def main():
	K = read_int()
	print(slv(K))

def __starting_point():
	main()
__starting_point()


import collections
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
K = int(input())

def ans():
	visited = [False] * K
	s = (1, 1)
	q = collections.deque()
	q.append(s)
	while True:
		c = q.popleft()
		visited[c[0]] = True
		if c[0] == 0:
			return c[1]
		if not visited[c[0] * 10 % K] and (not visited[c[0] * 10 % K]):
			q.appendleft((c[0] * 10 % K, c[1]))
		if not visited[(c[0] + 1) % K] and (not visited[(c[0] + 1) % K]):
			q.append(((c[0] + 1) % K, c[1] + 1))
print(ans())


from collections import deque

def bfs(K: int) -> list:
	hasChecked = [False] * (K + 1)
	cost_list = [0] * (K + 1)
	cost_list[1] = 1
	que = deque([(cost_list[1], 1)])
	while que:
		(cost, res) = que.popleft()
		if hasChecked[res]:
			continue
		hasChecked[res] = True
		cost_list[res] = cost
		if not hasChecked[10 * res % K]:
			que.appendleft((cost, 10 * res % K))
		if not hasChecked[(res + 1) % K]:
			que.append((cost + 1, (res + 1) % K))
	return cost_list
K = int(input())
cost_list = bfs(K)
print(cost_list[0])


from collections import deque
K = int(input())
q = deque()
q.append((1, 1))
visited = [False] * K
ans = 0
while ans == 0:
	(s, x) = q.popleft()
	if visited[x]:
		continue
	visited[x] = True
	if x == 0:
		ans = s
		break
	q.appendleft((s, 10 * x % K))
	q.append((s + 1, (x + 1) % K))
print(ans)


K = int(input())
a = K
while a % 2 == 0:
	a //= 2
while a % 5 == 0:
	a //= 5
if a == 1:
	print(1)
else:
	mod = set([])
	a = 1
	while a not in mod:
		mod.add(a)
		a *= 10
		a %= K
	mod = list(mod)
	n = len(mod)
	wei = pow(2, K) - 1
	check = 1
	ans = 0
	for j in range(0, n):
		ans = ans | check << mod[j]
	check = ans
	for i in range(1, 46):
		if check >> 0 & 1 == 1:
			print(i)
			exit()
		ans = check
		for j in range(0, n):
			ans = ans | check << mod[j]
		ans1 = ans & wei
		ans2 = ans >> K
		check = ans1 | ans2


from heapq import heappush, heappop

def dijkstra(graph: list, node: int, start: int) -> list:
	inf = float('inf')
	dist = [inf] * node
	dist[start] = 0
	heap = [(0, start)]
	while heap:
		(cost, thisNode) = heappop(heap)
		for (NextCost, NextNode) in graph[thisNode]:
			dist_cand = dist[thisNode] + NextCost
			if dist_cand < dist[NextNode]:
				dist[NextNode] = dist_cand
				heappush(heap, (dist[NextNode], NextNode))
	return dist
K = int(input())
g = [[] for _ in range(K)]
for n in range(1, K + 1):
	g[n % K] += [(1, (n + 1) % K), (0, 10 * n % K)]
print(dijkstra(g, K, 1)[0] + 1)


from collections import defaultdict
import sys, heapq, bisect, math, itertools, string, queue, datetime
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** (-7)

def inpl():
	return list(map(int, input().split()))

def inpl_s():
	return list(input().split())
K = int(input())
lines = defaultdict(set)
for i in range(K - 1):
	lines[i].add((i + 1, 1))
lines[K - 1].add((0, 1))
for s in range(K):
	t = s * 10 % K
	if s != t:
		lines[s].add((t, 0))

def search(s, w_0):
	nonlocal weight
	nonlocal q
	for line in list(lines[s]):
		t = line[0]
		w = w_0 + line[1]
		if weight[t] > w:
			heapq.heappush(q, [w, t])
			weight[t] = w
s = 1
weight = [INF] * K
weight[s] = 0
q = [[0, s]]
heapq.heapify(q)
while q:
	(w, n) = heapq.heappop(q)
	search(n, w)
print(weight[0] + 1)


import sys
from heapq import heappush, heappop
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def input():
	return sys.stdin.readline().rstrip()

def main():

	def dijkstra(start, n, edges):
		d = [INF] * n
		used = [False] * n
		d[start] = 0
		used[start] = True
		edgelist = []
		for edge in edges[start]:
			heappush(edgelist, edge)
		while edgelist:
			minedge = heappop(edgelist)
			if used[minedge[1]]:
				continue
			v = minedge[1]
			d[v] = minedge[0]
			used[v] = True
			for edge in edges[v]:
				if not used[edge[1]]:
					heappush(edgelist, (edge[0] + d[v], edge[1]))
		return d
	K = int(input())
	edges = [[] for _ in range(K)]
	for i in range(K):
		edges[i].append((1, (i + 1) % K))
		edges[i].append((0, i * 10 % K))
	d = dijkstra(1, K, edges)
	print(d[0] + 1)
main()


import heapq

def generate_graph(K):
	return [{(i + 1) % K: 1, i * 10 % K: 0} for i in range(K)]

def dijkstra(start, goal, graph):
	answer = [float('inf')] * len(graph)
	answer[start] = 0
	remains = sorted([[v, i] for (i, v) in enumerate(answer)])
	while remains:
		(_, i) = heapq.heappop(remains)
		for (j, cost) in list(graph[i].items()):
			if answer[j] > answer[i] + cost:
				answer[j] = answer[i] + cost
				heapq.heappush(remains, [answer[j], j])
	return answer[goal] + 1
K = int(input())
graph = generate_graph(K)
print(dijkstra(1, 0, graph))


import sys
INF = 1 << 60
MOD = 10 ** 9 + 7
sys.setrecursionlimit(2147483647)
input = lambda : sys.stdin.readline().rstrip()
from collections import deque

def resolve():
	k = int(input())
	dist = [INF] * k
	dist[1] = 1
	queue = deque([1])
	while queue:
		v = queue.pop()
		if dist[10 * v % k] > dist[v]:
			dist[10 * v % k] = dist[v]
			queue.appendleft(10 * v % k)
		if dist[(v + 1) % k] > dist[v] + 1:
			dist[(v + 1) % k] = dist[v] + 1
			queue.append((v + 1) % k)
	print(dist[0])
resolve()


from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, deque
from bisect import bisect
from random import *

def read():
	return int(input())

def reads():
	return [int(x) for x in input().split()]
INF = 1 << 60

def bfs(K):
	result = [INF] * K
	result[1] = 1
	que = deque([(1, 1)])
	while len(que) > 0:
		(d, u) = que.popleft()
		if result[u] < d:
			continue
		v0 = 10 * u % K
		if d < result[v0]:
			result[v0] = d
			que.appendleft((d, v0))
		v1 = (u + 1) % K
		if d + 1 < result[v1]:
			result[v1] = d + 1
			que.append((d + 1, v1))
	return result

def solve(k):
	return bfs(k)[0]
K = read()
print(solve(K))


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 5)

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

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
from collections import deque
k = ni()
que = deque([(1, 1)])
kmod = [0] * k
while kmod[0] == 0:
	(cost, idx) = que.popleft()
	if kmod[idx] == 0:
		kmod[idx] = cost
		que.appendleft((cost, 10 * idx % k))
		que.append((cost + 1, (idx + 1) % k))
print(kmod[0])


import collections
n = int(input())
cursor = 1
deque = collections.deque([(cursor, 0)])
visited = {cursor}
min_path = 100000000000.0
while len(deque) > 0:
	(cursor, min_path) = deque.popleft()
	visited.add(cursor)
	if cursor == 0:
		break
	(pone, mten) = ((cursor + 1) % n, cursor * 10 % n)
	if not pone in visited:
		deque.append((pone, min_path + 1))
	if not mten in visited:
		deque.appendleft((mten, min_path))
print(min_path + 1)


from collections import deque
K = int(input())
visited = [False] * K
s = (1, 1)
q = deque()
q.append(s)
while True:
	c = q.popleft()
	visited[c[0]] = True
	if c[0] == 0:
		print(c[1])
		return
	if not visited[c[0] * 10 % K] and (not visited[c[0] * 10 % K]):
		q.appendleft((c[0] * 10 % K, c[1]))
	if not visited[(c[0] + 1) % K] and (not visited[(c[0] + 1) % K]):
		q.append(((c[0] + 1) % K, c[1] + 1))


from collections import deque
k = int(input())
d = deque()
mat = []
for i in range(k):
	mat.append([])
dis = [10 ** 18] * k
dis[1] = 0
for i in range(k):
	mat[i].append(((i + 1) % k, True))
	if 10 * i % k != i:
		mat[i].append((10 * i % k, False))
d.append(1)
res = 0
while d:
	left = d.popleft()
	for (neighbour, edge) in mat[left]:
		distance = edge + dis[left]
		if dis[neighbour] > distance:
			dis[neighbour] = distance
			if edge == 0:
				d.appendleft(neighbour)
			else:
				d.append(neighbour)
print(dis[0] + 1)


from collections import deque

def bfs01(K, adjlist):
	reached = [False] * K
	d = deque()
	d.append((1, 0))
	reached[1] = True
	while True:
		cur = d.popleft()
		reached[cur[0]] = True
		if cur[0] == 0:
			return cur[1]
		for (j, w) in adjlist[cur[0]]:
			if w == 0:
				if not reached[j]:
					d.appendleft((j, cur[1]))
			elif w == 1:
				if not reached[j]:
					d.append((j, cur[1] + 1))
K = int(input())
adjlist = [[] for _ in range(K)]
for i in range(K):
	to1 = (i + 1) % K
	to2 = 10 * i % K
	if to1 == to2:
		adjlist[i] = [(to2, 0)]
	else:
		adjlist[i] = [(to1, 1), (to2, 0)]
print(bfs01(K, adjlist) + 1)


from collections import deque
n = int(input())
mins = [1000 for i in range(n + 1)]
used = [0 for i in range(n + 1)]
deq = deque()
deq.append((1, 1))
while deq:
	(x, cnt) = deq.popleft()
	mins[x] = min(mins[x], cnt)
	used[x] = 1
	if used[10 * x % n] == 0:
		deq.appendleft((10 * x % n, cnt))
	if used[(x + 1) % n] == 0:
		deq.append(((x + 1) % n, cnt + 1))
print(mins[0])


from collections import deque

def main():
	K = int(input())
	ans = sum_digits(K)
	for i in range(2, 10):
		ans = min(ans, sum_digits(K * i))
	print(ans)

def sum_digits(n):
	return sum(map(int, list(str(n))))

def main2():
	import sys
	debug = sys.argv[-1] == 'debug'
	K = int(input())
	q = deque([1])
	inf = float('inf')
	dp = [inf for _ in range(K)]
	dp[1] = 0
	while q:
		idx = q.popleft()
		x = dp[idx]
		m1 = idx * 10 % K
		m2 = (idx + 1) % K
		if dp[m1] > x:
			dp[m1] = x
			q.appendleft(m1)
		if dp[m2] > x + 1:
			dp[m2] = x + 1
			q.append(m2)
		if debug:
			print((m1, m2), dp, q, file=sys.stderr)
			print('-' * 10, file=sys.stderr)
	print(dp[0] + 1)
main2()


import sys
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
K = int(readline())
edges = [[] for _ in range(K)]
INF = 10 ** 31
dist = [INF] * K
for i in range(K):
	edges[i].append(((i + 1) % K, 1))
	j = 10 * i % K
	if i != j:
		edges[i].append((j, 0))
q = deque([1])
dist[1] = 0
while q:
	x = q.popleft()
	for (y, c) in edges[x]:
		d = dist[x] + c
		if d < dist[y]:
			dist[y] = d
			if c == 1:
				q.append(y)
			else:
				q.appendleft(y)
print(dist[0] + 1)


from collections import deque

def solve(k):
	que = deque()
	que.append((1, 1))
	dp = {1: 1}
	while que:
		(x, c) = que.pop()
		y = (x + 1) % k
		if not y in dp or dp[y] > c + 1:
			dp[y] = c + 1
			que.appendleft((y, c + 1))
		z = 10 * x % k
		if not z in dp or dp[z] > c:
			dp[z] = c
			que.append((z, c))
	return dp[0]
k = int(input())
print(solve(k))


from collections import deque

def foo(k):
	q = deque([(1, 0)])
	nodes = {}
	while q:
		(x, cost) = q.popleft()
		if x in nodes:
			continue
		nodes[x] = cost
		zero = x * 10 % k
		one = (x + 1) % k
		q.appendleft((zero, cost))
		q.append((one, cost + 1))
	return nodes[0]
k = int(input())
print(foo(k) + 1)


from heapq import heappop, heappush
from collections import deque
k = int(input())
inf = float('inf')
data = [[] for i in range(k)]
for i in range(1, k):
	if i % 10 == 9:
		data[i] = [[i * 10 % k, 0]]
	else:
		data[i] = [[i * 10 % k, 0], [(i + 1) % k, 1]]
que = deque([[1, 1]])
ans = [inf] * k
while que:
	(c, u) = que.popleft()
	ans[u] = c
	for (v, d) in data[u]:
		if ans[v] == inf:
			if d == 0:
				que.appendleft([c, v])
			else:
				que.append([c + 1, v])
	if ans[0] != inf:
		break
print(ans[0])


from collections import deque
K = int(input())
cost = [-1] * K
deq = deque([(1, 1)])
while deq:
	(x, d) = deq.popleft()
	if cost[x] >= 0:
		continue
	cost[x] = d
	if x == 0:
		break
	for (y, c) in [(10 * x % K, 0), ((x + 1) % K, 1)]:
		if c:
			deq.append((y, d + 1))
		else:
			deq.appendleft((y, d))
print(cost[0])


import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline
k = int(input())
g = [[] for _ in range(k)]
for i in range(k):
	g[i].append(((i + 1) % k, 1))
	if i:
		g[i].append((10 * i % k, 0))
from heapq import *

def dijkstra(g, start):
	n = len(g)
	dist = [float('inf')] * n
	pending = n - 1
	dist[start] = 0
	q = [(0, start)]
	while q and pending:
		(c, v) = heappop(q)
		if dist[v] < c:
			continue
		pending -= 1
		for (to, cost) in g[v]:
			if dist[v] + cost < dist[to]:
				dist[to] = dist[v] + cost
				heappush(q, (dist[to], to))
	return dist
dist = dijkstra(g, 1)
print(dist[0] + 1)


import sys
import heapq
INF = float('inf')

class Graph(object):

	def __init__(self, N):
		self.N = N
		self.V = list(range(N))
		self.E = [[] for _ in range(N)]

	def add_edge(self, edge):
		if len(edge) == 2:
			edge.append(1)
		elif len(edge) != 3:
			print('error in add_edge')
			pass
		(s, t, w) = edge
		self.E[s].append([t, w])
		pass

def shortestPath(g: Graph, s: int):
	dist = [INF] * g.N
	dist[s] = 0
	prev = [None] * g.N
	Q = []
	heapq.heappush(Q, (dist[s], s))
	while len(Q) > 0:
		(_, u) = heapq.heappop(Q)
		for (v, w) in g.E[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				prev[v] = u
				heapq.heappush(Q, (dist[v], v))
	return (dist, prev)

def solve(K: int):
	g = Graph(K)
	for i in range(1, K):
		g.add_edge([i, (i + 1) % K, 1])
		g.add_edge([i, 10 * i % K, 0])
	(dist, prev) = shortestPath(g, 1)
	print(dist[0] + 1)
	return

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	K = int(next(tokens))
	solve(K)
main()


k = int(input())
import heapq
INF = 10 ** 9

class Dijkstra:

	def __init__(self, adj):
		self.adj = adj
		self.num = len(adj)
		self.dist = [INF] * self.num
		self.prev = [INF] * self.num
		self.q = []

	def calc(self, start):
		self.dist[start] = 0
		heapq.heappush(self.q, (0, start))
		while len(self.q) != 0:
			(prov_cost, src) = heapq.heappop(self.q)
			if self.dist[src] < prov_cost:
				continue
			for (dest, cost) in self.adj[src]:
				if self.dist[dest] > self.dist[src] + cost:
					self.dist[dest] = self.dist[src] + cost
					heapq.heappush(self.q, (self.dist[dest], dest))
					self.prev[dest] = src
		return self.dist
edge = [[] for _ in range(k)]
for i in range(k):
	edge[i].append([(i + 1) % k, 1])
	edge[i].append([i * 10 % k, 0])
DIJ = Dijkstra(edge)
DIJ.calc
print(DIJ.calc(1)[0] + 1)


import sys
K = int(input())
graph = [[] for _ in range(K)]
for i in range(K):
	graph[i].append(((i + 1) % K, 1))
	graph[i].append((10 * i % K, 0))
dist = [-1] * K
(s, t) = (1, 0)
queue = [s]
d = 0
while queue:
	new_queue = set()
	while queue:
		q = queue.pop()
		if dist[q] == -1:
			dist[q] = d
			for (v, w) in graph[q]:
				if w == 0:
					queue.append(v)
				else:
					new_queue.add(v)
	d += 1
	queue = list(new_queue)
print(dist[0] + 1)


k = int(input())
ones = set()
x = 1
while not x in ones:
	ones.add(x)
	x = x * 10 % k
num = 1
mask = (1 << k) - 1
for i in range(1, 46):
	next = 0
	for j in ones:
		next |= num << j
	num = next & mask | next >> k
	if num % 2 == 1:
		print(i)
		exit()


import sys
sys.setrecursionlimit(2147483647)
INF = float('inf')
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().rstrip()
from collections import deque

def resolve():
	k = int(input())
	E = [[] for _ in range(k)]
	for i in range(k):
		E[i].append(((i + 1) % k, 1))
		E[i].append((10 * i % k, 0))
	dist = [INF] * k
	dist[1] = 0
	Q = deque([1])
	while Q:
		v = Q.popleft()
		for (nv, w) in E[v]:
			if dist[nv] <= dist[v] + w:
				continue
			dist[nv] = dist[v] + w
			if w == 0:
				Q.appendleft(nv)
			else:
				Q.append(nv)
	print(dist[0] + 1)
resolve()


import sys
from collections import deque

def input():
	return sys.stdin.readline()[:-1]

def inputi():
	return int(input())
K = inputi()
vals = [10 ** 5 + 1] * K
visit = []
vals[1] = 0
q = deque([1])
flag = False
while len(q) > 0:
	s = q.popleft()
	vs = vals[s]
	if s == 0:
		print(vs + 1)
		flag = True
		break
	s0 = 10 * s % K
	if vs < vals[s0]:
		vals[s0] = vs
		q.appendleft(s0)
	s1 = (s + 1) % K
	if vs + 1 < vals[s1]:
		vals[s1] = vs + 1
		q.append(s1)


import sys
input = sys.stdin.readline
from collections import deque
K = int(input())
D = [-1] * K
q = deque()
q.append(1)
D[1] = 1
while q:
	p = q.pop()
	n1 = p * 10 % K
	if D[n1] == -1 or D[n1] > D[p]:
		D[n1] = D[p]
		q.append(n1)
	n2 = (p + 1) % K
	if D[n2] == -1:
		D[n2] = D[p] + 1
		q.appendleft(n2)
print(D[0])


from collections import defaultdict, deque
INF = float('inf')
K = int(input())

def zero_one_bfs_shortest_path(s, K):
	G = defaultdict(list)
	for v in range(K):
		G[v].append((0, v * 10 % K))
		G[v].append((1, (v + 1) % K))
	d = [INF] * K
	d[s] = 0
	dq = deque()
	dq.appendleft(s)
	while len(dq) != 0:
		u = dq.popleft()
		for (w, v) in G[u]:
			if d[v] > d[u] + w:
				d[v] = d[u] + w
				if w == 0:
					dq.appendleft(v)
				else:
					dq.append(v)
	return d
print(zero_one_bfs_shortest_path(1, K)[0] + 1)


import heapq

def small_multiple(k):
	dist = [float('inf')] * k
	q = []
	heapq.heappush(q, (1, 1))
	while q:
		(n, c) = heapq.heappop(q)
		if dist[n] <= c:
			continue
		dist[n] = c
		if dist[(n + 1) % k] > c + 1:
			heapq.heappush(q, ((n + 1) % k, c + 1))
		if dist[n * 10 % k] > c:
			heapq.heappush(q, (n * 10 % k, c))
	print(dist[0])

def main():
	k = int(input())
	small_multiple(k)
main()


from collections import deque
q = deque()
ans = {}
K = int(input())
q.append((1, 1))
while len(q):
	(resid, total) = q.popleft()
	if resid in ans:
		continue
	ans[resid] = total
	q.appendleft((resid * 10 % K, total))
	q.append(((resid + 1) % K, total + 1))
print(ans[0])


from collections import deque
import sys
try:
	from typing import Deque, List
except ImportError:
	pass

def solve(K: int):
	pars = list(range(K))

	def union(a: int, b: int):
		pars[a] = b

	def getpar(a: int):
		if pars[a] == a:
			return a
		pars[a] = getpar(pars[a])
		return pars[a]
	for i in range(K):
		union(getpar(i), getpar(i * 10 % K))
	gs = [getpar(i) for i in range(K)]
	if gs[0] == gs[1]:
		print(1)
		return
	G = [[] for i in range(K)]
	for i in range(K):
		G[gs[i]].append(gs[(i + 1) % K])
	d = {gs[1]: 1}
	q = deque()
	q.append(gs[1])
	while q:
		s = q.popleft()
		for t in G[s]:
			if t in d:
				continue
			d[t] = d[s] + 1
			if t == gs[0]:
				print(d[t])
				return
			q.append(t)
	assert False

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	K = int(next(tokens))
	solve(K)
main()


from collections import deque
k = int(input())
e = [[] for i in range(k)]
for i in range(k):
	e[i].append(((i + 1) % k, 1))
	if i * 10 % k != i:
		e[i].append((i * 10 % k, 0))
d = [-1] * k
d[1] = 0
q = deque([])
q.append((1, 0))
while q:
	(now, dis) = q.popleft()
	for (nex, cost) in e[now]:
		if d[nex] == -1 or d[nex] > dis + cost:
			d[nex] = dis + cost
			if cost == 0:
				q.appendleft((nex, dis))
			else:
				q.append((nex, dis + 1))
print(d[0] + 1)


import collections
K = int(input())
Q = collections.deque([(1, 1)])
searched = set()
while True:
	(n, d) = Q.popleft()
	r = n % K
	if not r in searched:
		if r == 0:
			break
		else:
			searched.add(r)
			Q.append((n + 1, d + 1))
			Q.appendleft((n * 10 % K, d))
print(d)


def loop(i):
	j = 10 * i % K
	if dp[i] < dp[j - 1] + 1 and dp[i] < dp[j]:
		dp[j] = dp[i]
		return (j, True)
	if dp[j - 1] + 1 < dp[i] and dp[j - 1] + 1 < dp[j]:
		dp[j] = dp[j - 1] + 1
		return (j, True)
	return (j, False)
K = int(input())
dp = [K + 1 for _ in range(K)]
dp[1] = 1
for i in range(1, K):
	if i == 1:
		pass
	else:
		dp[i] = min(dp[i - 1] + 1, dp[i])
	l = i
	while True:
		(l, updated) = loop(l)
		if not updated:
			break
dp[0] = min(dp[K - 1] + 1, dp[0])
print(dp[0])


k = int(input())
INF = 10 ** 6
d = [INF for _ in range(k)]
d[1] = 1
temp = [[1, 1]]
while 1:
	next = []
	for (p, c) in temp:
		if c + 1 < d[(p + 1) % k]:
			d[(p + 1) % k] = c + 1
			next.append([(p + 1) % k, c + 1])
		if c < d[p * 10 % k]:
			d[p * 10 % k] = c
			next.append([p * 10 % k, c])
	if len(next) == 0:
		break
	else:
		temp = [] + next
print(d[0])


import io
import math
import scipy.sparse
import numpy
from collections import deque
q = deque()
K = int(input())
q += [(1, 1)]
m = {}
while len(q):
	(n, s) = q.pop()
	if not n in m:
		m[n] = s
		q += [(n * 10 % K, s)]
		q.appendleft(((n + 1) % K, s + 1))
print(m[0])


from collections import deque
K = int(input())
G = [[] for i in range(K)]
for n in range(K):
	G[n].append([(n + 1) % K, 1])
	G[n].append([10 * n % K, 0])
que = deque([[1, 1]])
dist = [float('inf')] * K
while que:
	(node, cost) = que.pop()
	dist[node] = min(cost, dist[node])
	for (e, e_cost) in G[node]:
		if dist[e] != float('inf'):
			continue
		if e_cost == 0:
			que.append([e, cost + 0])
		if e_cost == 1:
			que.appendleft([e, cost + 1])
print(dist[0])


from collections import *
q = deque([(1, 1)])
k = int(input())
m = {}
while q:
	(n, s) = q.pop()
	if (n in m) - 1:
		m[n] = s
		q += ((n * 10 % k, s),)
		q.appendleft((-~n % k, s + 1))
print(m[0])


import sys

def I():
	return int(sys.stdin.readline().rstrip())
K = I()
Graph = [0] * K
for i in range(K):
	if (i + 1) % K != 10 * i % K:
		Graph[i] = [((i + 1) % K, 1), (10 * i % K, 0)]
	else:
		Graph[i] = [(10 * i % K, 0)]
from collections import deque
q = deque([1])
d = [100] * K
d[1] = 1
while q:
	n = q.pop()
	if n == 0:
		continue
	else:
		for (a, b) in Graph[n]:
			if d[a] > d[n] + b:
				d[a] = d[n] + b
				if b == 0:
					q.append(a)
				else:
					q.appendleft(a)
print(d[0])


from collections import deque
k = int(input())
d = [-1] * (k * 10)
d[0] = 0
q = deque([0])
ans = 100000000
while q:
	p = q.pop()
	(x, r) = (p // 10, p % 10)
	if r < 9:
		t = (x + 1) % k * 10 + r + 1
		if t // 10 == 0:
			ans = min(ans, d[p] + 1)
		elif d[t] == -1:
			q.appendleft(t)
			d[t] = d[p] + 1
	t = x * 10 % k * 10
	if d[p] != 0 and t // 10 == 0:
		ans = min(ans, d[p])
	elif d[t] == -1:
		q.append(t)
		d[t] = d[p]
print(ans)


from collections import deque
K = int(input())
INF = 10 ** 9
res = [INF] * K
res[1] = 1
q = deque()
q.append(1)
while q:
	r = q.popleft()
	if r == 0:
		break
	nr = (r + 1) % K
	if res[r] < res[nr]:
		res[nr] = res[r] + 1
		q.append(nr)
	nr = 10 * r % K
	if res[r] < res[nr]:
		res[nr] = res[r]
		q.appendleft(nr)
print(res[0])


from heapq import heappush, heappop
K = int(input())
INF = float('inf')
d = [INF] * K
G = [[] for i in range(K)]
for i in range(K):
	G[i].append(((i + 1) % K, 1))
	G[i].append((10 * i % K, 0))
d[1] = 0
que = [(1, 0)]
while que:
	(v, cost) = heappop(que)
	if d[v] < cost:
		continue
	for (w, c) in G[v]:
		if d[w] > d[v] + c:
			d[w] = d[v] + c
			heappush(que, (w, d[w]))
print(d[0] + 1)