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

print((solve(K)))



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

print((solve(K)))
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(eval(input()))
print((solve(K)))

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(eval(input()))
print((solve(K)))

-from collections import deque +def solve(K): +    checked = [False] * K +    def calc(x): +        while not checked[x]: +            checked[x] = True +            yield x +            x = (x * 10) % K -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 +    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