#include <iostream>
#include <iomanip>
#include <climits>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#include <unordered_map>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <random>
#define _USE_MATH_DEFINES
#include <math.h>

using namespace std;

#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e15
#define _INFLL (long long)-1e15
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> P;

struct graph_t {
	int n;           // |V|, index begins with 0
	int m;           // |E|
	vector<P> edges; // E
	vector<ll> cost; // cost or distance
	vector<ll> cap;  // capacity
};

class Dijkstra {
private:
	struct node {
		int id; bool done; vi to_eid; vi to; vll cost; int from_eid; int from; ll d;
		bool operator<(const node & another) const {
			return !(d != another.d ? d < another.d : id < another.id);
		}
	};
	vector<node> nodes;
	int n, source;
	bool _01bfs_flag;
public:
	Dijkstra(graph_t G, int start) {
		n = G.n;
		nodes.resize(n);
		Loop(i, n) nodes[i] = { i, false,{},{},{}, -1, -1, INFLL };
		_01bfs_flag = false;
		Loop(i, G.edges.size()) {
			nodes[G.edges[i].first].to_eid.push_back(i);
			nodes[G.edges[i].first].to.push_back(G.edges[i].second);
			if (G.cost[i] > 1) _01bfs_flag = false;
			nodes[G.edges[i].first].cost.push_back(G.cost[i]);
		}
		source = start;
		nodes[source].d = 0;
		deque<node> deq;
		priority_queue<node> pq;
		_01bfs_flag ? deq.push_front(nodes[source]) : pq.push(nodes[source]);
		while (_01bfs_flag? deq.size() : pq.size()) {
			node a = _01bfs_flag ? deq.front() : pq.top();
			_01bfs_flag ? deq.pop_front() : pq.pop();
			if (nodes[a.id].done) continue;
			nodes[a.id].done = true;
			Loop(j, a.to.size()) {
				node *b = &nodes[a.to[j]];
				if (b->done) continue;
				ll buf = a.d + a.cost[j];
				if (buf < b->d) {
					b->d = buf;
					b->from_eid = a.to_eid[j];
					b->from = a.id;
					_01bfs_flag ? (b->d ? deq.push_back(*b) : deq.push_front(*b)) : pq.push(*b);
				}
			}
		}
		return;
	}
	vi get_path(int v) {
		stack<int> stk;
		stk.push(v);
		int a = v;
		while (nodes[a].from != -1) {
			stk.push(nodes[a].from);
			a = nodes[a].from;
		}
		if (a != source) return{ -1 };
		vi ret;
		while (stk.size()) {
			ret.push_back(stk.top());
			stk.pop();
		}
		return ret;
	}
	vi get_path_eid(int v) {
		stack<int> stk;
		int a = v;
		while (nodes[a].from != -1) {
			stk.push(nodes[a].from_eid);
			a = nodes[a].from;
		}
		if (a != source) return{ -1 };
		vi ret;
		while (stk.size()) {
			ret.push_back(stk.top());
			stk.pop();
		}
		return ret;
	}
	ll get_dist(int v) {
		return nodes[v].d;
	}
};

int main() {
	int n; cin >> n;
	graph_t G;
	G.n = n;
	Loop1(i, n - 1) {
		if (i % 10 != 9) {
			G.edges.push_back({ i, (i + 1) % n });
			G.cost.push_back(1);
		}
		G.edges.push_back({ i, i * 10 % n });
		G.cost.push_back(0);
	}
	Dijkstra dijkstra(G, 1);
	cout <<  dijkstra.get_dist(0) + 1 << endl;
	return 0;
}

Measured memory_bytes: 36192