package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"strconv"
)

var (
	readString func() string
	readBytes  func() []byte
	stdout     *bufio.Writer
)

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

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

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

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

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

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

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 eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

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

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

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

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

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

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

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func gcd64(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd64(b, a%b)
}

// readString() string
// readInt() int
// readInt64() int64
// readFloat64() float64

// -----------------------------------------------------------------------------

func main() {
	defer stdout.Flush()
	K := readInt()
	G := make([][]Edge, K)
	for i := 1; i < K; i++ {
		G[i] = append(G[i], Edge{(i + 1) % K, 1})
		G[i] = append(G[i], Edge{(i * 10) % K, 0})
	}

	q := NewDeque()
	d := make([]int, K)
	for i := range d {
		d[i] = math.MaxInt32
	}
	d[1] = 0
	for _, e := range G[1] {
		if d[1]+e.cost < d[e.to] {
			d[e.to] = d[1] + e.cost
			if e.cost == 0 {
				q.PushFront(e.to)
			} else {
				q.PushBack(e.to)
			}
		}
	}
	for !q.Empty() {
		v := q.PopFront()
		if v == 0 {
			println(d[0] + 1)
			return
		}
		for _, e := range G[v] {
			if d[v]+e.cost < d[e.to] {
				d[e.to] = d[v] + e.cost
				if e.cost == 0 {
					q.PushFront(e.to)
				} else {
					q.PushBack(e.to)
				}
			}
		}
	}
}

type Edge struct {
	to, cost int
}

// -----------------------------------------------------------------------------

type Deque struct {
	a    []int
	l, r int
}

func NewDeque() *Deque {
	return &Deque{
		a: make([]int, 8),
		l: 0,
		r: 1,
	}
}

func (d *Deque) expand() {
	olen := d.Len()
	na := make([]int, len(d.a)*2)
	if d.l < d.r {
		copy(na, d.a[d.l+1:d.r])
	} else {
		copy(na, d.a[d.l+1:len(d.a)])
		copy(na[len(d.a)-d.l-1:], d.a[0:d.r])
	}
	d.a = na
	d.l = len(d.a) - 1
	d.r = olen
}

func (d *Deque) isFull() bool {
	return d.l == d.r
}

func (d *Deque) PushFront(v int) {
	if d.isFull() {
		d.expand()
	}
	d.a[d.l] = v
	if d.l == 0 {
		d.l = len(d.a)
	}
	d.l--
}

func (d *Deque) PushBack(v int) {
	if d.isFull() {
		d.expand()
	}
	d.a[d.r] = v
	if d.r == len(d.a)-1 {
		d.r = -1
	}
	d.r++
}

func (d *Deque) Empty() bool {
	return (d.l+1)%len(d.a) == d.r
}

func (d *Deque) PopFront() int {
	i := (d.l + 1) % len(d.a)
	if i == d.r {
		panic("empty queue")
	}
	v := d.a[i]
	d.l = i
	return v
}

func (d *Deque) PopBack() int {
	i := d.r - 1
	if i < 0 {
		i = len(d.a) - 1
	}
	if i == d.l {
		panic("empty queue")
	}
	v := d.a[i]
	d.r = i
	return v
}

func (d *Deque) Len() int {
	if d.l < d.r {
		return d.r - d.l - 1
	}
	return (len(d.a) - d.l - 1) + d.r
}

func (d *Deque) At(i int) int {
	if d.Len() <= i {
		panic("out of index")
	}
	j := (d.l + i + 1) % len(d.a)
	return d.a[j]
}


Measured memory_bytes: 9088