//#define debug //*******************************************************************************************************************************************

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// [Tips]
// XCodeでのEOF入力はCtrl+D
// ¥はAlt+\
// ansは結構INTの範囲2,147,483,647を超えることがあるのでlong long使っておいたほうが良い
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////




////////////////////////////////////////
//ABC077
//D - Small Multiple
//
//整数の問題をグラフの最短経路問題に帰着させるという素人には非常に発想が難しい問題
//Dijkstra Algorithm (with priority_queue) で実装
////////////////////////////////////////


#ifdef debug
#include <chrono>
#endif

#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstring> //memcpy
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
#include <map>
//#include <unordered_map> //hash func.
#include <fstream> //ifstream, ofstream
#include <iterator> //insert_iterator::inserter
#include <set>


//#define NDEBUG //If NDEBUG is defined before #include <cassert>, assert will be ignored. You had better define NDEBUG when u submit the code.
#include <cassert> //assert

using namespace std;


#define dout cout
//If u wanna output to a text file instead of standard output, plz define OUTPUTFILE.
//#define OUTPUTFILE "output.txt" //************************************************************
#ifdef OUTPUTFILE
#define dout outputfile
ofstream outputfile(OUTPUTFILE);
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif


#define din cin
//If u wanna input from a text file instead of standard input, plz define INPUTFROMTEXTFILEを.
//#define INPUTFILE "input.txt" //**************************************************************
#ifdef INPUTFILE
#define din inputfile
ifstream inputfile(INPUTFILE);
#endif

#define scand(A) scanf("%d", &(A))
#define scans(A) scanf("%s", (A))
#define printd(A) printf("%d\n", (A))
#define prints(A) printf("%s\n", (A))
#define disp(A) dout << #A << " = " << setw(3) << (A) << endl
#define disP(A) dout << setw(3) << (A) << " "
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define show(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(A[j]);} dout << endl
#define showi(A,s,g) dout << #A << " = "; rep(j, (s), (g)) {disP(j);} dout << endl
#define line  dout << "----------------\n"
#define line2 dout << "================\n"

#define sign(x) ((x)>0)-((x)<0) //x<0: -1, x=0: 0, x>0: +1
#define p(i) ((i)/2)
#define l(i) ((i)*2)
#define r(i) ((i)*2+1)
#define sibling(i) (i^1) //the other sibling of i (ex. 16^1 = 17, 17^1 = 16)
#define isRightChild(i) (i&1) // ex. 16&1 = 0, 17&1 = 1
#define isLeftChild(i) (!(i&1)) // ex. 16&1 = 1, 17&1 = 0

int dx[] = {1, 0, -1,  0};
int dy[] = {0, 1,  0, -1};

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

const int INF = (1LL<<31)-1;
const int NONE = -1;
//const ll INF_LL = (ll)9e18-1LL; //Be careful for overflow.
//const ull INF_ULL = (ull)1e19-1ULL;
//#define MOD 1000000007 //大きい素数の代表といえばこの人、10億7さん

#define N_MAX 100010 //num of vertex or element
//#define M_MAX 124760 //num of edge
//#define DATA_MAX 1010


int N;
#define mod(i) ((i)%N)


struct Node {
    int id;
    vector<Node*> nextNodeThroughEdge;
    vi costOfEdge;
    int minDistFromNode1;
    Node* predecessor; //0からの最短経路において、1つ前のノードid
    int prevEdgeId; //predecessorからこのノードに来るときに使った、predecessor内のedge id
    bool done; //dijkstraで確定したノードはtrueにする
    
    //当初はこのoperator<のオーバロードで、priority_queueを使おうと考えていたが、
    //dijkstraの中で、minDistFromNode1 が動的に更新されてしまうので、priority_queueの挙動がおかしくなるので却下
    //よって、このoperator<は結局使わない
    bool operator < (const Node &p) const { //for priority_queue
        return this->minDistFromNode1 > p.minDistFromNode1; //distが "最小" のノードを最優先で取り出したいので、priority_queueの仕様上、不等号が逆向きになることに注意!!
    }
    
    
    void display() {
        line;
        disp(id);
        dout << setw(3) << id << " を *10 すると、" << nextNodeThroughEdge[0]->id << " : cost=" << costOfEdge[0] << endl;
        dout << setw(3) << id << " を  +1 すると、" << nextNodeThroughEdge[1]->id << " : cost=" << costOfEdge[1] << endl;
        disp(minDistFromNode1);
        if(predecessor!=NULL) disp(predecessor->id);
        disp(prevEdgeId);
        disp(done);
        dout << endl;
    }
    
} V[N_MAX];





void init() {
    rep(i,0,N) {
        V[i].id = i;
        
        //整数idを10倍する操作 = コスト0
        V[i].nextNodeThroughEdge.push_back(&V[mod(i*10)]);
        V[i].costOfEdge.push_back(0);
        
        //整数idを+1する操作 = コスト1
        V[i].nextNodeThroughEdge.push_back(&V[mod(i+1)]);
        V[i].costOfEdge.push_back(1);
        
        if(i==1) V[i].minDistFromNode1 = 0;
        else V[i].minDistFromNode1 = INF;
        
        V[i].predecessor = NULL;
        V[i].prevEdgeId = NONE;
        V[i].done = false;
    }
}



void display() {
#ifdef debug
    line2;
    rep(i,0,N) V[i].display();
    
#endif
}


int solve_dijkstra() {
    
#ifdef debug
    dout << "//////////////////////////// solve_dijkstra() /////////////////////////////\n";
#endif
    
    //Node*内のコスト値は動的に更新されるので、キューのキーとしては使えない
    //各瞬間のコストをわざわざ取り出して、ペアにして、キューに追加する (さすればキーが後から動的に更新されない)
    priority_queue<pair<int, Node*>, vector<pair<int, Node*> >, greater<pair<int, Node*> > > Q;
    
    Q.push(make_pair(0, &V[1])); //start node (cost = 0)
    
    
    while(not Q.empty()) {
        pair<int, Node*> vv = Q.top(); Q.pop();
        Node* v = vv.second;
        
        
#ifdef debug
        line2;
        dout << "以下のノードがQの中でコスト最小なので、このノードからhopできるノードのコストを更新する\n";
        disp(vv.first);
        v->display();
#endif
        
        if(v->done) {
#ifdef debug
            dout << "本ノードはすでに確定済みなので、無視する\n";
#endif
            continue;
        }
        
        //本ノードを確定させる
        v->done = true;
        
        
        //update next hop info.
        rep(i,0,v->nextNodeThroughEdge.size()) {
            
            if( v->minDistFromNode1 + v->costOfEdge[i] < v->nextNodeThroughEdge[i]->minDistFromNode1 ) { //コストがより小さい値で更新できそうであれば
                v->nextNodeThroughEdge[i]->minDistFromNode1 = v->minDistFromNode1 + v->costOfEdge[i];
                v->nextNodeThroughEdge[i]->predecessor = v;
                v->nextNodeThroughEdge[i]->prevEdgeId = i;
            }
            
            
            //next hopノードが「未確定」ノードであれば、コストが更新されたかされていないかの如何によらず、next hopノードをQに追加
            //同じノードがだぶってQに追加されることもあるが、コスト最小のものから取り出されて、そのときに「確定」されるので、問題ない
            if(v->nextNodeThroughEdge[i]->done==false)
                Q.push(make_pair(v->nextNodeThroughEdge[i]->minDistFromNode1, v->nextNodeThroughEdge[i]));
                //今この瞬間のコストをわざわざ取り出して、それを元にキューに追加する (さすればキーが後から動的に更新されない)
            
            
#ifdef debug
            dout << "--- update -- ";
            disp(i);
            v->nextNodeThroughEdge[i]->display();
#endif
        } //end of rep
        
//        dout << "1連のupdateが終了\n";
//        display();
        
        
        
    } //end of while-loop (Q)
    
    
    return V[0].minDistFromNode1 + 1;
    
}




int main() {
    
    //cin, coutの高速化  ＊注意：cinを使うなら全部cinで、scanfを使うなら全部scanfで統一するように！
    cin.tie(0); //cinとcoutの同期を切る
    ios::sync_with_stdio(false); //iostreamとstdioの同期を切る
    
    //read input data
    //    scand(N);
    din >> N;
    
    
    //------------------------------------------------------------------------------------------
    #ifdef debug
    //start timer
    auto startTime = chrono::system_clock::now();
    #endif
    //------------------------------------------------------------------------------------------
    
    
    
    init();
    display();
    
    int ans = 1;
    if(N!=1) ans = solve_dijkstra();
    
#ifdef debug
    dout << "//////////////////////////////////// solve_dijkstra()実施後の状態 /////////////////////////////////////////\n";
#endif
    display();
    
    
    
#ifdef debug
    dout << "=== OUTPUT ===\n";
#endif
    
    dout << ans << endl;
    

#ifdef debug
    //最短経路の復元
    Node* p = &V[0];
    vi path;
    while(p->predecessor!=NULL) {
        path.push_back(p->prevEdgeId);
        p = p->predecessor;
    }
    
    reverse(path.begin(), path.end());
    show(path, 0, path.size());
    
    int ansK = 1;
    rep(i,0,path.size()) {
        if(path[i]==0) {
            ansK *= 10;
        } else {
            assert(path[i]==1);
            ansK++;
        }
    }
    
    disp(ansK);
    assert(mod(ansK)==0);
    
#endif
    
    
    
    //------------------------------------------------------------------------------------------
    #ifdef debug
    //stop timer
    auto endTime = chrono::system_clock::now();
    auto dur = endTime - startTime;
    auto msec = chrono::duration_cast<chrono::milliseconds>(dur).count();
    dout << fixed << setprecision(4) << (double)msec/1000 << " sec \n";
    #endif
    //------------------------------------------------------------------------------------------
    
#ifdef INPUTFILE
    inputfile.close();
#endif
    
#ifdef OUTPUTFILE
    outputfile.close();
    cout << "\"" << OutputFilePath << "\"" << endl;
#endif
    
    return 0;
}




Measured memory_bytes: 15484