from collections import deque



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



if __name__=='__main__':

    main()

from collections import deque

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


if __name__ == "__main__":
    main()

+import sys -k = int(eval(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)) +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)) + + +if __name__ == "__main__": +    main()