package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
  "container/heap"
)

var (
	readString func() string
	stdout     *bufio.Writer
)

func init() {
	readString = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = readInt()
	}
	return b
}

func readLengthAndSlice() []int {
	n := readInt()
	return readIntSlice(n)
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

func minInt(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func minUint(a, b uint) uint {
	if a < b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func minUint64(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func maxInt(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func maxUint(a, b uint) uint {
	if a < b {
		return b
	}
	return a
}
func maxInt64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func maxUint64(a, b uint64) uint64 {
	if a < b {
		return b
	}
	return a
}

func absInt(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

// readString() string
// readInt() int
// readIntSlice(n int) []int
// readLengthAndSlice() []int

type edge struct {
	from, to, cost int
}

type Item struct {
	value    int
	priority int // The priority of the item in the queue.
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
	item := x.(*Item)
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(*pq)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

func main() {
	defer stdout.Flush()

	k := readInt()

	g := make([][]edge, k)
	for i := range g {
		g[i] = make([]edge, 2)
		g[i][0] = edge{i, (i + 1) % k, 1}
		g[i][1] = edge{i, (i * 10) % k, 0}
	}

	pq := new(PriorityQueue)

	push := func(cost, idx int) {
		heap.Push(pq, &Item{
			priority: cost,
			value:    idx,
		})
	}
	pop := func() (int, int) {
		item := heap.Pop(pq).(*Item)
		return item.priority, item.value
	}

	ans := make([]int, k)
	for i := range ans {
		ans[i] = math.MaxInt32
	}
	ans[1] = 0
	push(0, 1)
	for pq.Len() != 0 {
		cost, from := pop()
		if ans[from] < cost {
			continue
		}
		for _, e := range g[from] {
			if ans[e.from]+e.cost < ans[e.to] {
				ans[e.to] = ans[e.from] + e.cost
				push(ans[e.to], e.to)
			}
		}
	}

	println(ans[0] + 1)

}


Measured memory_bytes: 12800