#include <iostream>
#include <deque>

using namespace std;

int d[114514];

int main()
{
	int k;
	cin >> k;
	deque<int> q;
	for (int i = 0; i < k; i++)
		d[i] = i == 1 ? 0 : 100;
	q.push_back(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		for (int i = 0; i < 2; i++) {
			int v = (i ? u + 1 : u * 10) % k;
			int l = d[u] + i;
			if (d[v] <= l)
				continue;
			d[v] = l;
			i ? q.push_back(v) : q.push_front(v);
		}
	}
	cout << d[0] + 1 << endl;
	return 0;
}
