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

INF = 1 << 60

MOD = 10**9 + 7 # 998244353

sys.setrecursionlimit(2147483647)

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

def resolve():

    k = int(eval(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

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

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


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

-from collections import deque -    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) +    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)