//rng_58 bless me

#include<bits/stdc++.h>
using namespace std;
//define:
#define REP(i,n) for(int i = 0; i < n; i++)
//const:
const int MAXN = 100010;
//something:
int N;
int dis[MAXN];
bool vis[MAXN];
vector <pair <int,int> > g[MAXN];
void iint() {
	REP(i,N) {
		dis[i] = 2147483647;
	}
	dis[0] = 0;
}
void SPFA(int x) {
	iint();
	queue <int> q;
	q.push(x);
	vis[x] = 1;
	while(!q.empty()) {
		int f = q.front();
		q.pop();
		vis[f] = 0;
		REP(i,g[f].size()) {
			int nx = g[f][i].first;
			if(dis[nx] > dis[f] + g[f][i].second) {
				dis[nx] = dis[f] + g[f][i].second;
				if(!vis[nx]) {
					vis[nx] = 1;
					q.push(nx);
				}
			}
		}
	}
}
//run:
void solve() {
	cin >> N;
	for(int i = 1;i < N;i++) {
		REP(j,10) {
			g[i].push_back({((i - 1) * 10 + j) % N + 1,j});
		}
	}
	for(int i = 1;i <= 9;i++) {
		g[0].push_back({i + 1,i});
	}
	SPFA(0);
	cout << dis[1] << endl;
}
//times:
void Times(int T) {
	while(T--) {
		solve();
	}
}
//begin:
int main() {
	int T;
	T = 1;
	//cin >> T;
	Times(T);
	return 0;
}