#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<queue>
#include<set>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
int n,f[110000],q[510000],he,ta,x,y;
int main(){
	scanf("%d",&n);
	while (n%2==0) n/=2;
	while (n%5==0) n/=5;
	fo(i,0,n-1) f[i]=n;
	q[he=ta=n+n]=1%n;f[1%n]=1;//q[he=ta=n+n]=1
	while (he<=ta){
		x=q[he];he++;
		y=(x*10)%n;
		if (f[x]<f[y]){
			f[y]=f[x];
			q[--he]=y;
		}
		y=(x+1)%n;
		if (f[x]+1<f[y]){
			f[y]=f[x]+1;
			q[++ta]=y;
		}
	}
	//fo(i,0,n-1) printf("%d ",f[i]);
	printf("%d\n",f[0]);
	return 0;
}