// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <vector>

#include <algorithm>

#include <cstring>

#include <utility>

#include <cmath>

#include <ctime>

#include <cstdlib>

#include <queue>

using namespace std;

 

#define LL   long long

#define ld   long double

#define pii  pair<int,int>

#define pLL  pair<LL,LL>

#define vint vector<int>

#define vLL  vector<LL>

 

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

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

#define F first

#define S second

#define MP make_pair

#define PB push_back

 

#define Si(x) scanf("%d",&(x));

#define Sii(x,y) scanf("%d %d",&(x),&(y));

#define Siii(x,y,z) scanf("%d %d %d",&(x),&(y),&(z));

#define SL(x) scanf("%lld",&(x));

#define SLL(x,y) scanf("%lld %lld",&(x),&(y));

#define SLLL(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z));

 

#define Pi(x) printf("%d\n",(x));

#define Pii(x,y) printf("%d %d\n",(x),(y));

#define Piii(x,y,z) printf("%d %d %d\n",(x),(y),(z));

#define Piiii(x,y,z,w) printf("%d %d %d %d\n",(x),(y),(z),(w));

#define Piiiii(a,b,c,d,e) printf("%d %d %d %d %d\n",(a),(b),(c),(d),(e));

#define Piiiiii(a,b,c,d,e,f) printf("%d %d %d %d %d %d\n",(a),(b),(c),(d),(e),(f));

#define PL(x) printf("%lld\n",(x)*1LL);

#define PLL(x,y) printf("%lld %lld\n",(x)*1LL,(y)*1LL);

#define PLLL(x,y,z) printf("%lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL);

#define PLLLL(x,y,z,w) printf("%lld %lld %lld %lld\n",(x)*1LL,(y)*1LL,(z)*1LL,(w)*1LL);

 

#define Pi1(x) printf("%d",  (x));

#define PiL(x) printf("%lld",(x));

#define Pspace putchar(' ');

#define Pendl  puts("");

 

#define MEM0(x) memset( (x), 0, sizeof( (x) ) )

#define MEM1(x) memset( (x),-1, sizeof( (x) ) )

#define REP1(i,n)  for (int i = 1; (n) >= i ; ++i)

#define REP0(i,n)  for (int i = 0; (n) >  i ; ++i)

#define REP(L,R,k) for (int i = (L); (R) >= i; i+= (k) )

 

int myRnd(int L,int R) {

    return abs(( (rand()<<15)|rand() ) ) % (R-L+1) + L;

}

 

const int N = 1e5 + 6;

int dp[N];

 

int main () {

    srand(time(NULL));

    int k;

    Si(k);

    MEM1(dp);



    priority_queue<pii,vector<pii>,greater<pii> > pq;



    int ans=-1;

    for (int i=9;i>=1;i--) {

        dp[i%k] = i;

        pq.push({i,i%k});

    }

    while (!pq.empty()) {

        pii p=pq.top();

        pq.pop();



        if (dp[p.S] != p.F) continue;

        REP0(i,10) {

            int nxt=p.S*10+i;

            nxt %= k;



            if (nxt == 0) {

                if (ans == -1) ans = p.F + i;

                else ans = min(ans,p.F+i);

            }

            else {

                if (dp[nxt] == -1) {

                    dp[nxt] = p.F + i;

                    pq.push({dp[nxt],nxt});

                }

                else if (p.F + i < dp[nxt]) {

                    dp[nxt] = p.F + i;

                    pq.push({dp[nxt],nxt});

                }

            }

        }

    }

    Pi(ans);

}

// Faster C++ solution for the same problem (measured speedup: 2.028759643675243x):
/*

  code by RyeCatcher

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <utility>

#include <queue>

#include <vector>

#include <ext/pb_ds/hash_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

#include <iostream>

#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define ri register int

#define ll long long

#define ull unsigned long long

#define SIZE 1<<22

using std::min;

using std::max;

using std::deque;

using std::vector;

using std::pair;

using namespace __gnu_pbds;

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

template <class T>inline void read(T &x){

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn = 10000005;

const int inf=0x7fffffff;

typedef pair<int,int> pii;

bool vis[maxn];

deque<pii>q;

int k;

int main(){

	int x,y;

	read(k);

	q.push_back(pii(1,1));

	while(q.size()){

		x=q.front().first,y=q.front().second;q.pop_front();

		if(vis[x])continue;vis[x]=1;

		if(x==0){

			printf("%d\n",y);

			break;

		}

		q.push_front(pii(x*10%k,y));

		q.push_back(pii((x+1)%k,y+1));

	}

	return 0;

}