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



    # 0-1 BFS

    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

INF = 1 << 60

MOD = 10**9 + 7 # 998244353

sys.setrecursionlimit(2147483647)

input = lambda:sys.stdin.readline().rstrip()

from collections import deque

def resolve():

    k = int(eval(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()
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(eval(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))
    # 0-1 BFS
    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

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


def resolve():
    k = int(eval(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()

+INF = 1 << 60 +MOD = 10**9 + 7  # 998244353 -INF = float("inf") -MOD = 10**9 + 7 -    E = [[] for _ in range(k)] -    for i in range(k): -        E[i].append(((i + 1) % k, 1)) -        E[i].append(((10 * i) % k, 0)) -    # 0-1 BFS -    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)) +    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]))