package main

import (
	. "fmt"
	"bufio"
	"os"
	"strconv"
)

const INF int = 1e9
const LINF int64 = 1e9
const MOD int = INF + 7

func solve(g [][]pair) int {
	qu := NewPriorityQueue(true)
	min_cost := make([]int, len(g))
	for i := 0; i < len(min_cost); i++ {
		min_cost[i] = INF
	}
	min_cost[1] = 1
	qu.push(pair{1, 1})

	for !qu.empty() {
		p := qu.top()
		qu.pop()

		for _, e := range g[p.second] {
			if (p.first + e.second) >= min_cost[e.first] {
				continue
			}

			min_cost[e.first] = p.first + e.second
			qu.push(pair{min_cost[e.first], e.first})
		}
	}

	return min_cost[0]
}

func main() {
	next := NewScanner()
	k := next.Int()
	g := make([][]pair, k)
	for i := 1; i < k; i++ {
		g[i] = []pair{pair{(i + 1) % k, 1}, {(i * 10) % k, 0}}
	}

	Println(solve(g))
}

// Priority Queue
type PriorityQueue struct {
	comp bool
	data []pair
}

func NewPriorityQueue(comp bool) *PriorityQueue {
	return &PriorityQueue{comp, make([]pair, 0)}
}

func (qu *PriorityQueue) push(x pair) {
	n := len(qu.data)
	qu.data = append(qu.data, x)

	for n > 0 {
		par := (n - 1) / 2
		
		if qu.comp {
			if !Comp(qu.data[par], qu.data[n]) {
				qu.data[par], qu.data[n] = qu.data[n], qu.data[par]
			}
		} else {
			if Comp(qu.data[par], qu.data[n]) {
				qu.data[par], qu.data[n] = qu.data[n], qu.data[par]
			}
		}

		n = par
	}
}

func (qu *PriorityQueue) pop() {
	n := len(qu.data) - 1
	qu.data[0] = qu.data[n]
	qu.data = qu.data[:n]

	for i := 0;; {
		j := 2 * i + 1
		if j >= n {
			break
		}

		if qu.comp {
			if (j < n - 1) && !Comp(qu.data[j], qu.data[j + 1]) {
				j++
			}
		
			if !Comp(qu.data[i], qu.data[j]) {
				qu.data[i], qu.data[j] = qu.data[j], qu.data[i]
			}
		} else {
			if (j < n - 1) && Comp(qu.data[j], qu.data[j + 1]) {
				j++
			}

			if Comp(qu.data[i], qu.data[j]) {
				qu.data[i], qu.data[j] = qu.data[j], qu.data[i]
			}
		}

		i = j
	}
}

func (qu *PriorityQueue) top() pair {
	return qu.data[0]
}

func (qu *PriorityQueue) size() int {
	return len(qu.data)
}

func (qu *PriorityQueue) empty() bool {
	return len(qu.data) == 0
}

// Scanner begin
type scanner struct {
	r	*bufio.Reader
	buf []byte
	p	int
}

func NewScanner() *scanner {
	return &scanner{r: bufio.NewReaderSize(os.Stdin, 10000)}
}

func (s *scanner) next() string {
	s.pre()
	start := s.p

	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}

	result := string(s.buf[start:s.p])
	s.p++
	return result
}

func (s *scanner) Line() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)

	return string(s.buf[start:])
}

func (s *scanner) Int() int {
	v, _ := strconv.Atoi(s.next())
	return v
}

func (s *scanner) Int64() int64 {
	v, _ := strconv.ParseInt(s.next(), 10, 64)
	return v
}

func (s *scanner) Float() float32 {
	f, _ := strconv.ParseFloat(s.next(), 32)

	return float32(f)
}

func (s *scanner) Float64() float64 {
	f, _ := strconv.ParseFloat(s.next(), 64)

	return f
}

func (s *scanner) Bool() bool {
	b, _ := strconv.ParseBool(s.next())

	return b
}

func (s *scanner) String() string {
	return s.next()
}


func (s *scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}

func (s *scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}

// Scanner end

// Standard Function begin
func Itob(i int) bool {
	if i == 0 {
		return false
	} else {
		return true
	}
}

func Btoi(f bool) int {
	if f {
		return 1
	} else {
		return 0
	}
}

func min(a ...int) int {
	ret := a[0]
	for _, e := range a {
		if e < ret {
			ret = e
		}
	}

	return ret
}

func max(a ...int) int {
	ret := a[0]
	for _, e := range a {
		if e > ret {
			ret = e
		}
	}

	return ret
}

func minInt64(a ...int64) int64 {
	ret := a[0]
	for _, e := range a {
		if e < ret {
			ret = e
		}
	}

	return ret
}

func maxInt64(a ...int64) int64 {
	ret := a[0]
	for _, e := range a {
		if e > ret {
			ret = e
		}
	}

	return ret
}

func minFloat(a ...float32) float32 {
	ret := a[0]
	for _, e := range a {
		if e < ret {
			ret = e
		}
	}

	return ret
}

func maxFloat(a ...float32) float32 {
	ret := a[0]
	for _, e := range a {
		if e > ret {
			ret = e
		}
	}

	return ret
}

func minFloat64(a ...float64) float64 {
	ret := a[0]
	for _, e := range a {
		if e < ret {
			ret = e
		}
	}

	return ret
}

func maxFloat64(a ...float64) float64 {
	ret := a[0]
	for _, e := range a {
		if e > ret {
			ret = e
		}
	}

	return ret
}

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

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

func absFloat(a float32) float32 {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

func absFloat64(a float64) float64 {
	if a < 0 {
		return -a
	} else {
		return a
	}
}

// Standard Struct begin
type pair struct {
	first, second int
}

type pairs []pair

func Newpair() *pair {
	return &pair {
		first : 0,
		second : 0,
	}
}

func (p pair) String() string {
	return Sprint(p.first, p.second)
}

func (p pairs) Less(i, j int) bool {
	if p[i].first < p[j].first {
		return true
	} else if p[i].first == p[j].first {
		return p[i].second < p[j].second
	} else {
		return false
	}
}

func Comp(x, y pair) bool {
	if x.first < y.first {
		return true
	} else if x.first == y.first {
		return x.second < y.second
	} else {
		return false
	}
}

Measured memory_bytes: 10880