#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
const int N=2e5+10;
int k;int d[N];
struct node{
	int v,w;
};
vector<node>V[N];
bool vis[N];
bool operator >(node i,node j){
	return i.w>j.w;
}
priority_queue<node,vector<node>,greater<node> >q;
void jt(){
	for(int i=1;i<k;i++)
		for(int j=0;j<=9;j++)
			V[(i*10+j)%k].push_back(node{i,j});
}
void dij(){
	for(int i=0;i<k;i++)
		d[i]=inf,vis[i]=0;
	q.push((node){0,0});
	for(int i=1;i<k;i++){
		while(!q.empty()&&vis[q.top().v]) q.pop();
		if(q.empty()) break;
		int u=q.top().v;
		q.pop();
		vis[u]=1;
		for(node v:V[u])
			if(d[u]+v.w>d[v.v]){
				q.push((node){v.v,d[u]+v.w});
				d[v.v]=d[u]+v.w;
			}
	}
}
int main(){
	cin>>k;
	jt();dij();
	cout<<d[0];
	return 0;
}