#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef int TP;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const int MAXN =1e6+5;
const double PI=acos(-1);
void test() { cerr << "\n"; }
template <typename T,typename...Args>void test(T x,Args...args){cerr<<x<<" ";test(args...); }
inline ll qpow(ll a, ll b) {return b?((b&1)?a*qpow(a*a%MOD,b>>1)%MOD : qpow(a*a%MOD,b>>1))%MOD :1; }
inline ll qpow(ll a, ll b, ll c) {return b?((b&1)?a*qpow(a*a%c,b>>1)%c : qpow(a*a%c,b>>1)) % c: 1; }
inline ll gcd(ll a, ll b){return b?gcd(b,a% b): a; }
namespace Fast_IO
{ //orz laofu
    const int MAXL((1 << 18) + 1);
    char _io_ibuf[MAXL], *_io_iS, *_io_iT, _io_obuf[MAXL];
    char *_io_oS = _io_obuf, *_io_oT = _io_obuf + MAXL - 1, _io_c, _io_st[55];
    int _io_f, _io_tp;
    char Getchar(){
        if (_io_iS == _io_iT){
            _io_iS = _io_ibuf;_io_iT=_io_iS+fread(_io_ibuf,1,MAXL,stdin);
            return (_io_iS == _io_iT ? EOF : *_io_iS++);
        }else return (*_io_iS++);
    }
    void Write(){fwrite(_io_obuf,1,_io_oS-_io_obuf,stdout);_io_oS=_io_obuf;}
    void Putchar(char x){*_io_oS++ = x;if (_io_oS == _io_oT)Write();}
    inline int read(){
        int x=0;
        for(_io_f=1,_io_c=Getchar();_io_c<'0'||_io_c>'9';)_io_f=_io_c=='-'?-1:1,_io_c=Getchar();
        for(x=0;_io_c<='9'&&_io_c>='0';_io_c=Getchar())x=(x<<3)+(x<<1)+(_io_c^48);
        return x*_io_f;
    }
    inline long long read_ll(){
        long long x = 0;
        for(_io_f=1,_io_c=Getchar();_io_c<'0'||_io_c> '9';)_io_f=_io_c=='-'?-1:1,_io_c=Getchar();
        for(x=0;_io_c<='9'&&_io_c>='0';_io_c=Getchar())x=(x<<3)+(x<<1)+(_io_c^48);
        return x * _io_f;
    }
    template <class Int>
    void Print(Int x, char ch = '\0'){
        if (!x)Putchar('0');if (x < 0)Putchar('-'),x=-x;
        while(x)_io_st[++_io_tp]=x % 10 + '0', x /= 10;
        while(_io_tp)Putchar(_io_st[_io_tp--]);
        if (ch)Putchar(ch);
    }
    void Getstr(char *s, int &l){
        for(_io_c=Getchar();_io_c <'a'||_io_c>'z';)_io_c=Getchar();
        for(l=0;_io_c<='z'&&_io_c>='a';_io_c=Getchar())s[l++]=_io_c;
        s[l] = 0;
    }
    void Putstr(const char *s){for(int i=0,n=strlen(s);i<n;++i)Putchar(s[i]);}
} // namespace Fast_IO
using namespace Fast_IO;

struct Edge
{
    int from,to,cost,nxt;
}E[MAXN*2];
int cntE,head[MAXN];

int get(ll x)
{
    int ans=0;
    while(x)
    {
        ans+=x%10;
        x/=10;
    }
    return ans;
}
void addE(int a,int b,int c)
{
   // printf("%d %d %d\n",a,b,c);
    E[cntE]={a,b,c,head[a]};
    head[a]=cntE++;
}
int Dij(int s,int t)
{
    static int dist[MAXN];
    struct QNode{
        int dis,id;
        bool operator<(const QNode &R)const
        {
            return dis>R.dis;
        }
    };
    priority_queue<QNode>pq;
    memset(dist,0x3f,sizeof dist);
    dist[s]=0;pq.push({0,s});
    while(!pq.empty())
    {
        QNode tmp=pq.top();pq.pop();

        if(tmp.dis!=dist[tmp.id])continue;
        //printf("%d\n",tmp.id);
        for(int ei=head[tmp.id];ei!=-1;ei=E[ei].nxt)
        {
            if(dist[E[ei].to]>dist[tmp.id]+E[ei].cost)
            {
                dist[E[ei].to]=dist[tmp.id]+E[ei].cost;
             //   preval[E[ei].to]=E[ei].cost;
              //  pre[E[ei].to]=tmp.id;
                pq.push({dist[E[ei].to],E[ei].to});
            }
        }
    }
    int now=t;
//    while(now!=s)
//    {
//        printf("%d",preval[now]);
//        now=pre[now];
//    }
//    printf("\n");
    return dist[t];
}
void work()
{
    int n;scanf("%d",&n);
    if(n==100000){printf("1\n");return;}
    int s=100000,t=100001;
    for(int i=0;i<=t;i++)head[i]=-1;
    for(int i=1;i<=9;i++)
    {
        int val=n*i;
        addE(s,val/10,val%10);
    }
    for(int i=0;i<s;i++)
    {
        addE(i,t,get(i));
        for(int j=0;j<=9;j++)
        {
            addE(i,(i+n*j)/10,(i+n*j)%10);
        }
    }
    printf("%d\n",Dij(s,t));

}
int main()
{
   //std::ios::sync_with_stdio(false);
    //int T=read();for(int cas=1;cas<=T;cas++)
 // int T;scanf("%d",&T);for(int cas=1;cas<=T;cas++)
    work();
   // Write();
}
/**
8
0 -1
1 0
2 1
3 3
4 6
3 6
2 5
1 3


*/


Measured memory_bytes: 28020