#!/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))

#!/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))

#!/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))

#!/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))

-    n = f.read_int() -    d = [float("inf")] * n -    d[1] = 1 -    que = [(1, 1)]  # (min_dist, vertex) -    heapq.heapify(que) +    k = f.read_int() +    depth = [float("inf")] * k +    depth[1] = 1 +    que = collections.deque([1]) -        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] +        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]