// Slower C++ solution:
#define NDEBUG

#include <cassert>

#include <deque>

#include <functional>

#include <utility>



template <typename Key, typename T, class Compare = std::greater<Key>>

class _01Heap {

public:

	using key_type = Key;

	using mapped_type = T;

	using value_type = std::pair<key_type, mapped_type>;

	using reference = value_type &;

	using const_reference = const value_type &;

	using key_compare = Compare;

	using container_type = std::deque<value_type>;

	using size_type = typename container_type::size_type;

	class value_compare {

		friend class _01Heap;

		const key_compare comp;

		value_compare() : comp() {}



	public:

		constexpr bool operator()(const_reference x, const_reference y) const {

			return comp(x.first, y.first);

		}

	};



private:

	const value_compare comp;

	container_type dq;

	size_type size_;



public:

	_01Heap() : comp(), dq(), size_(0) {}

	const_reference top() const {

		assert(size_);

		return dq.front();

	}

	void pop() {

		assert(size_);

		--size_;

		dq.pop_front();

	}

	void push(const_reference x) {

		if (!size_)

			dq.push_front(x);

		else {

			assert(!comp(x, dq.front()) || !comp(dq.back(), x));

			if (comp(x, dq.front()))

				dq.push_back(x);

			else

				dq.push_front(x);

		}

		++size_;

	}

	size_type size() const noexcept { return size_; }

	bool empty() const noexcept { return !size_; }

};





struct edge {

	int to;

	int cost;

};

#include<iostream>

#include<vector>

#include<limits>

#include<tuple>

int main(void) {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	int k;

	std::cin >> k;

	std::vector<std::vector<edge>> G(k);

	for (int i = 0;i < k;++i) {

		G[i].push_back({ i * 10 % k,0 });

		G[i].push_back({ (i + 1) % k,1 });

	}

	_01Heap<int, int> Q;

	static constexpr int INF = std::numeric_limits<int>::max();

	std::vector<int> d(k, INF);

	Q.push({ 1,1 });

	d[1] = 1;

	int v, c;

	while (!Q.empty()) {

		std::tie(c, v) = Q.top();Q.pop();

		if (d[v] < c) continue;

		for (const auto &e : G[v]) {

			if (c + e.cost < d[e.to]) {

				d[e.to] = c + e.cost;

				Q.push({ d[e.to],e.to });

			}

		}

	}

	std::cout << d[0] << std::endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1134131346089748x):
//#define NDEBUG

#define _CRT_SECURE_NO_WARNINGS

#include <array>

#include <cstddef>

#include <cstdint>

#include <cstdio>

#include <limits>

#include <memory>

#include <string>

#include <type_traits>



template <class Integral> class Rirange;



template <class Integral = std::size_t> class irange {

public:

	using value_type = Integral;

	using reference = value_type &;

	using const_reference = const value_type &;

	class irangeitr {

		friend irange;

		value_type i;

		irangeitr(const value_type x) noexcept : i(x) {}



	public:

		void operator++() noexcept { ++i; }

		value_type &operator*() noexcept { return i; }

		const_reference operator*() const noexcept { return i; }

		bool operator!=(const irangeitr &x) const noexcept { return i < x.i; }

	};



private:

	const value_type f, l;



public:

	irange(const value_type first, const value_type last) noexcept

		: f(first), l(last) {}

	irangeitr begin() const noexcept { return irangeitr(f); }

	irangeitr end() const noexcept { return irangeitr(l); }

	Rirange<value_type> rev() const noexcept {

		return Rirange<value_type>(l - 1, f - 1);

	}

};

template <class Integral = std::size_t> class Rirange {

public:

	using value_type = Integral;

	using reference = value_type &;

	using const_reference = const value_type &;

	class Rirangeitr {

		friend Rirange;

		value_type i;

		Rirangeitr(const value_type x) noexcept : i(x) {}



	public:

		void operator++() noexcept { --i; }

		reference operator*() noexcept { return i; }

		const_reference operator*() const noexcept { return i; }

		bool operator!=(const Rirangeitr &x) const noexcept {

			return (!~x.i && ~i) || x.i < i;

		}

	};



private:

	const value_type f, l;



public:

	Rirange(const value_type x, const value_type y) noexcept : f(x), l(y) {}

	Rirangeitr begin() const noexcept { return Rirangeitr(f); }

	Rirangeitr end() const noexcept { return Rirangeitr(l); }

	irange<value_type> rev() const noexcept {

		return irange<value_type>(l + 1, f + 1);

	}

};



template <class T> bool maxi(T &a, const T &b) {

	if (b < a)

		return 0;

	a = b;

	return 1;

}

template <class T> bool mini(T &a, const T &b) {

	if (a < b)

		return 0;

	a = b;

	return 1;

}

template <class T> bool smaxi(T &a, const T &b) {

	if (a < b) {

		a = b;

		return 1;

	}

	return 0;

}

template <class T> bool smini(T &a, const T &b) {

	if (b < a) {

		a = b;

		return 1;

	}

	return 0;

}

struct customIO {

	int c;

	bool f;

	std::array<int, 30> buf;

	const std::array<int, 10> itoc;

	std::array<std::uint_least8_t, 256> ctoi_base;

	const std::uint_least8_t *const ctoi;

	void get_c() { c = fgetc(stdin); }

	void put_c(int x) { fputc(x, stdout); }

	bool vacant() { return c == ' ' || c == '\n'; }

	operator int() { return 0; }



	explicit customIO()

		: itoc({ '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' }),

		ctoi(std::addressof(ctoi_base[-static_cast<std::int_fast16_t>(

			std::numeric_limits<char>::min())])) {

		for (std::uint_least8_t i = 0; i < 10; ++i)

			ctoi_base[static_cast<int>("0123456789"[i]) -

			static_cast<std::int_fast16_t>(

				std::numeric_limits<char>::min())] = i;

	}

	// in



	void cueing() {

		while (get_c(), vacant())

			;

	}

	template <class T>

	auto operator>>(T &d) ->

		typename std::enable_if<std::is_signed<T>::value, customIO &>::type {

		d = 0;

		f = 0;

		cueing();

		if (c == '-')

			f = 1, get_c();

		do

			d = d * 10 + ctoi[c];

		while (get_c(), !vacant());

		if (f)

			d = -d;

		return *this;

	}

	template <class T>

	auto operator>>(T &d) ->

		typename std::enable_if<!std::is_signed<T>::value, customIO &>::type {

		d = 0;

		cueing();

		do

			d = d * 10 + ctoi[c];

		while (get_c(), !vacant());

		return *this;

	}

	customIO &operator>>(char &d) {

		cueing();

		d = c;

		return *this;

	}

	customIO &operator>>(double &d) {

		scanf("%lf", &d);

		return *this;

	}

	customIO &operator>>(std::string &d) {

		d.clear();

		cueing();

		do

			d.push_back(c);

		while (get_c(), !vacant());

		return *this;

	}

	template <class T> T input() {

		T d;

		*this >> d;

		return d;

	}



	// out



	template <class T>

	auto operator<<(T d) ->

		typename std::enable_if<std::is_signed<T>::value, customIO &>::type {

		c = 0;

		f = 0;

		if (d < static_cast<T>(0))

			f = 1, d = -d;

		while (d)

			buf[c++] = itoc[d % 10], d /= 10;

		if (!c)

			buf[c++] = itoc[0];

		if (f)

			put_c('-');

		while (c--)

			put_c(buf[c]);

		return *this;

	}

	template <class T>

	auto operator<<(T d) ->

		typename std::enable_if<!std::is_signed<T>::value, customIO &>::type {

		c = 0;

		while (d)

			buf[c++] = itoc[d % 10], d /= 10;

		if (!c)

			buf[c++] = itoc[0];

		while (c--)

			put_c(buf[c]);

		return *this;

	}

	customIO &operator<<(char d) {

		put_c(d);

		return *this;

	}

	customIO &operator<<(double d) {

		printf("%f", d);

		return *this;

	}

	customIO &operator<<(const std::string &d) {

		for (const auto e : d)

			put_c(e);

		return *this;

	}

	customIO &operator<<(const char *d) {

		while (*d != '\0')

			put_c(*(d++));

		return *this;

	}

	void endl() { put_c('\n'); }

	void space() { put_c(' '); }

} IO;



using int32 = std::int_fast32_t;

using int64 = std::int_fast64_t;

using uint32 = std::uint_fast32_t;

using uint64 = std::uint_fast64_t;

using intl32 = std::int_least32_t;

using intl64 = std::int_least64_t;

using uintl32 = std::uint_least32_t;

using uintl64 = std::uint_least64_t;

#include <cassert>

#include <deque>

#include <functional>

#include <utility>



template <class T>

using Heap01DefaultContainer = std::deque<T, std::allocator<T>>;



template <class T, template <class> class Container = Heap01DefaultContainer,

	class Compare = std::greater<typename Container<T>::value_type>>

	class Heap01 {

	public:

		using container_type = Container<T>;

		using value_type = typename container_type::value_type;

		using value_compare = Compare;

		using reference = typename container_type::reference;

		using const_reference = typename container_type::const_reference;

		using size_type = typename container_type::size_type;



	private:

		container_type c;

		value_compare comp;



	public:

		Heap01() : c(), comp() {}

		Heap01(const value_compare &x, const container_type &other)

			: c(other), comp(x) {}

		Heap01(const value_compare &x, container_type &&other)

			: c(std::move(other)), comp(x) {}



		bool empty() const noexcept { return c.empty(); }

		size_type size() const noexcept { return c.size(); }



		const_reference top() const {

			assert(!empty());

			return c.front();

		}



		void push(const value_type &x) {

			assert(empty() || !comp(x, c.front()) || !comp(c.back(), x));

			if (empty() || comp(x, c.front()))

				c.push_back(x);

			else

				c.push_front(x);

		}

		void push(value_type &&x) {

			assert(empty() || !comp(x, c.front()) || !comp(c.back(), x));

			if (empty() || comp(x, c.front()))

				c.push_back(std::move(x));

			else

				c.push_front(std::move(x));

		}

		template <class... Args> void emplace(Args &&... args) {

			value_type x(std::forward<Args>(args)...);

			assert(empty() || !comp(x, c.front()) || !comp(c.back(), x));

			if (empty() || comp(x, c.front()))

				c.push_back(std::move(x));

			else

				c.push_front(std::move(x));

		}

		void pop() {

			assert(!empty());

			c.pop_front();

		}

};







struct D {

	uint32 pos, dist;

	D(uint32 x, uint32 y) :pos(x), dist(y) {}

	bool operator>(const D &o)const {

		return dist > o.dist;

	}

};



#include<vector>

#include<tuple>

#include<utility>



int main() {

	const auto k = IO.input<uint32>();

	std::vector<uint32> d(k, UINT32_MAX / 2);

	d[1] = 1;

	Heap01<D> Q;

	Q.emplace(1, 1);

	while (!Q.empty()) {

		const D t = Q.top();

		Q.pop();

		if (t.dist <= d[t.pos]) {

			if (smini(d[t.pos * 10 % k], t.dist))

				Q.emplace(t.pos * 10 % k, t.dist);

			if (smini(d[(t.pos + 1) % k], t.dist + 1))

				Q.emplace((t.pos + 1) % k, t.dist + 1);

		}

	}

	IO << d[0] << '\n';

	return 0;

}