// Original C++ solution (slower):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define reg register

typedef long long ll;

const int MN=2e5;

struct edge{int t,nxt,c;}es[(MN<<1)+5];

int h[MN+5],cnt;

inline void ins(int s,int t,int c){es[++cnt]=(edge){t,h[s],c};h[s]=cnt;}

int dis[MN+5],q[MN+5],he,ta;

bool inq[MN];

inline void SPFA(){

	memset(dis,0x3f,sizeof(dis));

	he=ta=0;q[ta++]=inq[1]=dis[1]=1;

	while(he!=ta){

		reg int v=q[he++];he%=MN;

		for(reg int i=h[v];~i;i=es[i].nxt)

			if(dis[es[i].t]>dis[v]+es[i].c){

				dis[es[i].t]=dis[v]+es[i].c;

				if(!inq[es[i].t]){

					inq[es[i].t]=1;

					if(dis[es[i].t]<dis[q[he]])he=(he-1)%MN,q[he]=es[i].t;

					else q[ta++]=es[i].t,ta%=MN;

				}

			}

		inq[v]=0;

	}

}

int main(){

	memset(h,-1,sizeof(h));int k;scanf("%d",&k);

	for(reg int i=1;i<k;i++){

		ins(i,(i*10)%k,0);if((i+1)%10)ins(i,(i+1)%k,1);

	}

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

    return 0;

}

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

//#pragma GCC optimize(3)



#define X first

#define Y second

#define PB push_back

#define MP make_pair

#define mset(var,val) memset(var,val,sizeof(var))

#define IOS ios::sync_with_stdio(false);cin.tie(0)



#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)

#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

#define rep(i,n) for(int i = 0; i < n; ++i)

#define rep1(i,n) for(int i = 1; i <= n; ++i)



using namespace std;

typedef long long ll;



namespace debug {

#ifdef local

#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

#else

#define dbg(...)

#endif

void err() {

    cout << endl;

}

template<template<typename...> class T, typename t, typename... Args>

void err(T<t> a, Args... args) {

    for (auto x: a)

        cout << x << ' ';

    err(args...);

}

template<typename T, typename... Args>

void err(T a, Args... args) {

    cout << a << ' ';

    err(args...);

}

}



namespace stdio_input {

#define scd(args...) do{scanf_int(args);} while(0)

void scanf_int() {}

template<typename T, typename... Args>

void scanf_int(T &a, Args&... args) {

    scanf("%d", &a);

    scanf_int(args...);

}

#define scl(args...) do{scanf_ll(args);} while(0)

void scanf_ll() {}

template<typename T, typename... Args>

void scanf_ll(T &a, Args&... args) {

    scanf("%lld", &a);

    scanf_ll(args...);

}

#define scf(args...) do{scanf_double(args);} while(0)

void scanf_double() {}

template<typename T, typename... Args>

void scanf_double(T &a, Args&... args) {

    scanf("%lf", &a);

    scanf_double(args...);

}

}



namespace const_var {

const int inf = 0x3f3f3f3f;

const long long INF = 0x3f3f3f3f3f3f3f3fLL;

const double PI = acos(-1.0);

const int N = 1e5+10;

const long double eps = 1e-20;

const int mod = 1e9+7;

}



using namespace debug;

using namespace stdio_input;

using namespace const_var;



int T = 0;

void testcase() {

    cout << "Case #" << (++T) << ": ";

}



int dis[N];

bool vis[N];



struct P{

    int u, w;

    bool operator < (const P & b) const {

        return w > b.w;

    }

};



priority_queue<P> q;

void work() {

    int k;

    cin >> k;

    mset(dis, inf);

    dis[1] = 1;

    q.push({1,1});

    while(!q.empty()){

        int u = q.top().u;

        int w = q.top().w;

        q.pop();

        if(u == 0) break;

        if(vis[u] || dis[u] != w) continue;

        vis[u] = true;

        int v = u * 10 % k;

        if(dis[u] < dis[v]){

            dis[v] = dis[u];

            q.push({v, dis[v]});

        }

        v = (u + 1) % k;

        if(dis[u] + 1 < dis[v]){

            dis[v] = dis[u] + 1;

            q.push({v, dis[v]});

        }

    }

    cout << dis[0] << endl;

}



int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.sql","w",stdout);

#endif // local

    IOS;

//    getPrime();

//    init();

    int t;

//    cin >> t;

//    cin.get();

//    for(;t--;)

    work();

    return 0;

}


// Fastest known solution for this problem: