# Original solution
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    n = f.read_int()
    d = [float('inf')] * n
    d[1] = 1

    que = [(1, 1)]     # (min_dist, vertex)
    heapq.heapify(que)

    while len(que) > 0:
        dist, v0 = heapq.heappop(que)
        if d[v0] < dist: continue

        v1 = (v0*10) % n
        if d[v1] > d[v0]:
            d[v1] = d[v0]
            heapq.heappush(que, (d[v1], v1))

        v2 = (v0+1) % n
        if d[v2] > d[v0] + 1:
            d[v2] = d[v0] + 1
            heapq.heappush(que, (d[v2], v2))

    return d[0]


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else input()

    def next_case(self):
        next(self.file)
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return int(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return list(map(int, self.__readline().split()))
    def read_float_list(self): return list(map(float, self.__readline().split()))
    def read_long_list(self): return list(map(int, self.__readline().split()))
    def read_decimal_list(self): return list(map(decimal.Decimal, self.__readline().split()))
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print("Case #%d\n"%f.case, solve(f))
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print(solve(f))


# Optimized solution
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def solve(f):
    k = f.read_int()

    depth = [float('inf')] * k
    depth[1] = 1

    que = collections.deque([1])
    while len(que) > 0:
        num = que.popleft()
        n1 = (num*10)%k
        if depth[n1] > depth[num]:
            depth[n1] = depth[num]
            que.appendleft(n1)
        n2 = (num+1)%k
        if depth[n2] > depth[num]+1:
            depth[n2] = depth[num]+1
            que.append(n2)

    return depth[0]


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else input()

    def next_case(self):
        next(self.file)
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return int(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return list(map(int, self.__readline().split()))
    def read_float_list(self): return list(map(float, self.__readline().split()))
    def read_long_list(self): return list(map(int, self.__readline().split()))
    def read_decimal_list(self): return list(map(decimal.Decimal, self.__readline().split()))
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print("Case #%d\n"%f.case, solve(f))
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print(solve(f))