// Original C++ solution (slower):
/*****************

 *   I<3   C++   *

 *  IWANT ANYAC  *

 * ILOVEPROGRAM! *

 *IT'SINTERESTING*

 * ILOVEPROGRAM! *

 *  INCONTESTS   *

 *   GETSCORE    *

 *    ACCODE     *

 *     LETS      *

 *      GO       *

 *Written by:    *

 *    charlieyan *

 *****************/

#include <assert.h>

#include <ctype.h>

#include <errno.h>

#include <float.h>

#include <fstream>

#include <iomanip>

#include <iostream>

#include <limits>

#include <locale>

#include <math.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

#include <wchar.h>

#include <wctype.h>

#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <complex.h>

#include <fenv.h>

#include <inttypes.h>

#include <stdbool.h>

#include <stdint.h>

#include <tgmath.h>

#include <numeric>

#include <list>

#define LL long long

#define pb push_back

#define pob pop_back

#define mp make_pair

#define FILL(a,v) memset((void*)a,v,sizeof(a))

#define FILL0(a) FILL(a,0)

#define FILL1(a) FILL(a,-1)

#define FILLBIG(a) FILL(a,0x7f)

#define ALL(a) (a).begin(),(a).end()

#define Inf ((int)0x7f7f7f7f)

#define INF ((long long)0x7f7f7f7f7f7f7f7f)

#define Mod 1000000007

#define foreach(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)

#define FOR(i,x) for(int i=0;i<x;i++)

#define RFOR(i,x) for(int i=x-1;i>=0;i--)

#define FFOR(i,a,b) for(int i=a;i<b;i++)

#define FRFOR(i,a,b) for(int i=a-1;i>=b;i--)

#define SZ(a) ((int)(a).size())

#define FI first

#define SE second

#define OVER(a) return puts(a),0

#define fastio ios::sync_with_stdio(0)

#define filei(f) freopen(f,"r",stdin)

#define fileo(f) freopen(f,"w",stdout)

#define eprintf(...) fprintf(stderr,__VA_ARGS__)

#define MASK(a) (1<<(a))

#define MASKX(x,a) ((x)<<(a))

#define BIT(a,b) ((a>>b)&1)

#define cddx(a) priority_queue<a >

#define cxdd(a) priority_queue<a,vector<a >,greater<a > >

#define deval(a) {cerr<<#a<<" = "<<a<<endl;}

#define dearr(be,en) {cerr<<#be;cerr<<" = {";for(auto i=be;i!=en;i++)cerr<<' '<<*i;cerr<<" }\n";}

#define reg register

using namespace std;

typedef pair<int,int> pii;

typedef unsigned long long UINT;

typedef unsigned int uint;

typedef long long INT;

typedef long double ldouble;

typedef pair<INT,INT> PII;

typedef stringstream sst;

typedef istringstream iss;

typedef vector<int> vint;

typedef vector<INT> VINT;

typedef vector<pii> vpii;

typedef vector<PII> VPII;

typedef priority_queue<int> pqi;

typedef priority_queue<INT> PQI;

typedef priority_queue<pii> pqp;

typedef priority_queue<PII> PQP;

typedef priority_queue<int,vint,greater<int> > xqi;

typedef priority_queue<INT,VINT,greater<INT> > XQI;

typedef priority_queue<pii,vpii,greater<pii> > xqp;

typedef priority_queue<PII,VPII,greater<PII> > XQP;



int k,dis[100007];



void dij()

{

	FILLBIG(dis);

	xqp pq;

	pq.push(mp(0,k));

	dis[k]=0;

	while(pq.size())

	{

		pii m=pq.top();

		pq.pop();

		int ma=m.first,mb=m.second;

		if(ma!=dis[mb])continue;

		int mc=(mb*10)%k,md=(mb+1)%k;

		if(mb!=k&&dis[mc]>ma)

		{

			dis[mc]=ma;

			pq.push(mp(ma,mc));

		}

		if(dis[md]>ma+1)

		{

			dis[md]=ma+1;

			pq.push(mp(ma+1,md));

		}

	}

}



int main()

{

	scanf("%d",&k);

	dij();

	printf("%d\n",dis[0]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h> 

using namespace std;

struct P{int a,b;}q[200005];

int k,l=100000,r=100000;

bool book[100005];

int main(){

    scanf("%d", &k);

    q[l]={1,1};

    while(l<=r){

    	P x=q[l++];

        if(book[x.a]) continue; book[x.a]=1;

        if(x.a==0){printf("%d\n",x.b);break;}

        q[--l]={x.a*10%k,x.b};

        q[++r]={(x.a+1)%k,x.b+1};

    }

}

//首先我们会发现，任意一个数可以由1开始+1（数字总和+1）或*10（数字总和不变）来得到

//（x9+1是特例，但x9+1明显可以由更优的(x+1)0得到） 

//所以我们可以把数字看成一个个图，起点为x=1，那么按照x到x+1的边权为1 ，x到x*10的边权为0建图 

//那么我们的目标是什么呢？我们发现只要我们凑出一个数x，使x为k的倍数即可，那我们对于一个数字，如果它连向的数字为k的倍数

//我们就让它连向0，最终我们求的就是1到0的最短路

//这是一个01bfs，我们可以使用双端队列来解决 

//时间复杂度O(k) 

// Fastest known solution for this problem: