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: interview

Starter code:

Solutions:
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 collections import deque
K = int(input())
E = [[(i*10)%K,(i+1)%K] for i in range(K)] # E[i][0] がcost 0, E[i][1]がcost 1
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])

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

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra


class Graph(object):

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

    def add(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 to_csr(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))


K = int(input())
g = Graph(K)

for i in range(K):
    if i == K - 1:
        g.add(i, 0, 1)
    else:
        g.add(i, i + 1, 1)
    g.add(i, (i * 10) % K, 10**(-8))

d = dijkstra(g.to_csr(), directed=True, indices=1)
print(int(d[0]) + 1)

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

#!/usr/bin/env python3
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))


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


# coding: utf-8
# Your code here!

"""
01-BFS
辺の重みが0 or 1 のとき、dequeを使ってdijkstraを高速化できる
"""
from collections import deque
def bfs01(g,start):
    n = len(g)
    res = [float("inf")]*n #startからの最短距離
    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
        #if v==goal: break
        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

######################################################################
#ARC084 small multiple
#
######################################################################

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


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)
# https://img.atcoder.jp/arc084/editorial.pdf


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): #s->t
	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))


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

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


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

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


# 桁和最小の自然数は1
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))
        else:
            if c + 1 < d[nv]:
                d[nv] = c + 1
                dq.append((d[nv], nv))
print((d[0]))


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

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))
#print(graph)

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)
print(dist[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

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
que = deque([s])
dist[s] = 0
while que:
    v = que.popleft()
    d = dist[v]
    for w, c in G[v]:
        if d+c < dist[w]:
            dist[w] = d+c
            if c:
                que.append(w)
            else:
                que.appendleft(w)

print(dist[0]+1)

from collections import deque
k = int(input())
d = deque()
mat = []
for i in range(k):
    mat.append([])
#mark = [False]*k
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))

#bfs 1->0
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 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))

import queue


def bfs01(s: int, t: int, V: int, graph: list)->int:
    '''01-bfs
    :param s: source
    :param t: sink
    :param V: number of vertex
    :param graph: graph
    :return: minimum distance from `s` to `t`
    '''
    INF = float('inf')

    # deque と s から各頂点への距離を初期化する。
    q = queue.deque([])  # deque
    qc = 0               # 毎度 len(q) を回すと時間かかりそうなので変数で管理
    l = [INF] * V        # s から各頂点への距離

    # s に関する初期化
    q.append(s)
    qc += 1
    l[s] = 0

    # deque に頂点が存在する限り次を繰り返す。
    # 1. deque の先頭から頂点を取り出す。
    # 2. 取り出した頂点に隣接する全ての頂点に対して以下を行う。
    # 2-a. 距離が更新されるなら更新する。加えて辺の長さが 0 なら
    #      先頭に、1 なら末尾に追加する。
    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):
        # k -> k+1 に 1 の辺を、k -> 10*k に 0 の辺を張る。
        # ただし、どちらも mod K をとって 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


def __starting_point():
    K = int(input())
    ans = small_multiple(K)
    print(ans)

__starting_point()

#!/usr/bin/env python3
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):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        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):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    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):
        # 1を加える
        g.add_edge([i, (i+1) % K, 1])
        # 10倍する
        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))  # type: int
    solve(K)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
from collections import deque

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

# (辺の伸びる先, コスト)
G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1

# 01 - BFS
dist = [INF] * 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())
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))

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)

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

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

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)

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 sys
#import numpy as np
import itertools
from scipy.sparse import coo_matrix, lil_matrix
from scipy.sparse.csgraph import dijkstra, bellman_ford, floyd_warshall
#sys.setrecursionlimit(10000)

#H, W = [int(i) for i in input().split()]
N = int(input())

rows = []
cols = []
weights = []

"""
for _ in range(M):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)
"""

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()
#graph = coo_matrix((weights, (cols, rows)), shape=(10, 10)).tocsr()
#print(graph)
d1 = dijkstra(graph, indices=1, directed=True, unweighted=False)

print((int(d1[0]+1.5)))



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)

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


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


def __starting_point():
    main()

__starting_point()

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

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
        if kmod[10*idx%k] == 0:
            que.appendleft((cost, (10*idx%k)))
        if kmod[(idx+1)%k] == 0:
            que.append((cost+1, (idx+1)%k))            
        
print(kmod[0])

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)

from heapq import heappush, heappop


def dijkstra(graph: list, n: int, v_s: int, INF: int = float('inf')) -> list:
    # graph[v_from] = [(cost, v_to), ...]
    dist = [INF] * n

    dist[v_s] = 0
    heap = [(0, v_s)]  # heap = [(dist[v], v), ...]
    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)


import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(input())

# ある数に 1 を足すと各桁の和は 1 増える
# ある数に 10 を掛けると各桁の和は 0 増える
# mod K の世界で同じことやっても同じなので
# このグラフ上で 1 から 0 への最短距離が答え。

distances = [INF for _ in range(K)]

# 01BFS
distances[1] = 1
remains = deque()
remains.append((1, 1))
while True:
    d, mod_k = remains.popleft()
    if mod_k == 0:
        break
    if d + 1 < distances[(mod_k + 1) % K]:
        distances[(mod_k + 1) % K] = d + 1
        remains.append((d + 1, (mod_k + 1) % K))
    if d < distances[mod_k * 10 % K]:
        distances[mod_k * 10 % K] = d
        remains.appendleft((d, mod_k * 10 % K))
print((distances[0]))


import sys
from collections import deque

sys.setrecursionlimit(10000)
INF = float('inf')

K = int(input())

# ある数に 1 を足すと各桁の和は 1 増える
# ある数に 10 を掛けると各桁の和は 0 増える
# mod K の世界で同じことやっても同じなので
# このグラフ上で 1 から 0 への最短距離が答え。

distances = [INF for _ in range(K)]

# 01BFS
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 defaultdict
from heapq import heappop, heappush


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 list(self.graph.keys())


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()
N = int(input())
for i in range(N):
    g.add_edge(i, (i+1)%N, 1)
    g.add_edge(i, (10 * i) % N, 0)

d = Dijkstra(g, 1)
print((d.dist[0]+1))


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

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

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



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

# solution

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
q=deque();K=int(input());a=q.append;a((1,1));m={}
while len(q):
 n,s=q.popleft()
 if not n in m:m[n]=s;q.appendleft((n*10%K,s));a(((n+1)%K,s+1))
print(m[0])

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


def __starting_point():
    K = int(input())
    ans = small_multiple(K)
    print(ans)

__starting_point()

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

    if visited[v]:
        continue
    visited[v] = True

    Q.appendleft((s, (10 * v) % K))
    Q.append((s + 1, (v + 1) % K))

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

dist = []
for i in range(k):
    if i != k - 1:
        dist.append([i, i + 1, 1])
    else:
        dist.append([i, 0, 1])

for i in range(k):
    dist.append([i, (10 * i) % k, 0])

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):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]
# (src, dst, weight)
inputs = dist

g = Graph()
for src, dst, weight in inputs:
    g.add_edge(src, dst, weight)
    #g.add_edge(dst, src, weight)
spdi = {}

d = Dijkstra(g, 1)
sp = format(d.shortest_distance(0))
print(int(sp) + 1)

#!/usr/bin/env python3
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)]  # type: List[List[int]]
    for i in range(K):
        G[gs[i]].append(gs[(i + 1) % K])
    d = {gs[1]: 1}
    q = deque()  # type: Deque[int]
    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))  # type: int
    solve(K)


def __starting_point():
    main()

__starting_point()

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
q = deque()
K = int(input())
q.append((1, 1))
m = {}
while len(q):
 n, s = q.popleft()
 if n in m:continue
 m[n] = s
 q.appendleft((n * 10 % K, s))
 q.append(((n + 1) % K, s + 1))
print(m[0])

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)
            return
        ans=check
        for j in range(0,n):
            ans=ans|(check<<mod[j])
        ans1=ans&wei
        ans2=ans>>K
        check=ans1|ans2

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

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

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

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)

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)

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

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)

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


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 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 heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    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 deque

K = int(input())

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
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())

G = [((10*i % K, 0), ((i+1) % K, 1)) for i in range(K)]
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())
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))


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


from collections import deque
K=int(input())

d=[1000000 for x in range(K+1)]
d[1]=0

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]+1

print(bfs(K))

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

import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())

def MI(): return list(map(int, input().split()))
def MI1(): return list(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 math import ceil, floor, log2
from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    K = II()

    q = deque([(1, 1)])
    used = [0 for _ in range(K)]
    while len(q) > 0:
        # print(q)
        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))



def __starting_point():
    solve()

__starting_point()

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*
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])

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

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 deque
 
# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue
 
K = int(input())
q = deque()
q.append((1,1)) # 各桁の和、modulo K
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)


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

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 list(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:
    """ ダイクストラ高速化版(頂点数, 隣接リスト(0-indexed), 始点) """
    from heapq import heappush, heappop

    res = [INF] * N
    # スタート位置(今回は開始コストが0じゃないので1*Nを含める)
    que = [1*N+src]
    # 今回の開始位置1のコストは1
    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]))


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):#Gはi->jの辺をG[i]=[(j,cost),...]で保存
  INF=10**19
  n=len(G)
  d=[INF]*n#n=node数
  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))


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:
        # if (v+1)%K == 0:
        #     ans = w+1
        #     break
        d.append((w+1 ,(v+1)%K))
    if V[ (v*10)%K] == 0:
        d.appendleft((w, (v*10)%K))
        # if (v*10)%K == 0:
        #     ans = w
        #     break
print(ans)

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

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

from collections import deque
 
# 1から初めて、xがあるとき10x、x+1のいずれかが行えるとしてqueue
 
K = int(input())
q = deque()
q.append((1,1)) # 各桁の和、modulo K
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)


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


def __starting_point():
    main()

__starting_point()

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


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

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


#!/usr/bin/env python3
from collections import deque

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

# (辺の伸びる先, コスト)
G = [((10 * i % k, 0), ((i + 1) % k, 1)) for i in range(k)]
s = 1

# 01 - BFS
dist = [INF] * 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)

# -*- coding: utf-8 -*-
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()

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