// Original C++ solution (slower):
#include <bits/stdc++.h>



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

//using namespace __gnu_pbds;



const double pi = 3.141592653589793;



#define xx          first

#define yy          second

#define mp          make_pair

#define intl        long long

#define filein      freopen("input.txt", "r", stdin)

#define fileout     freopen("output.txt", "w", stdout)

#define debug       cout << "YES" << endl

#define what_is(x)  cout << #x << " is " << x << endl

#define pb          push_back

#define pii         pair<int, int>



//find_by_order(int) and order_of_key(int)

//typedef tree < intl , null_type ,less<intl>,rb_tree_tag,tree_order_statistics_node_update > ordered_set;

const int M = 345678;

int k, dist[123456];



int dijkstra()

{

    priority_queue<pii>q; //sum, rem

    memset( dist, 125, sizeof dist );

    for( int i = 1; i <= 9; i++ )

    {

        q.push( mp(-i,i) );

        dist[i] = i;

    }



    while( !q.empty() )

    {

        pii a = q.top();

        q.pop();

        int r = a.yy, s = dist[a.yy];

        if( r == 0 ) return s;

        for( int i = 0; i < 10; i++ )

        {

            int tr = (r*10 + i)%k;

            if( dist[tr] > s + i )

            {

                dist[tr] = s+i;

                q.push( mp( -dist[tr], tr ) );

            }

        }

    }

    //return dist[0];

}



int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    //filein;

    cin >> k;

    cout << dijkstra() << endl;

    return 0;

}


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



//#include <ext/pb_ds/assoc_container.hpp>

//#include <ext/pb_ds/tree_policy.hpp>



using namespace std;

//using namespace __gnu_pbds;



const double pi = 3.141592653589793;



#define xx          first

#define yy          second

#define mp          make_pair

#define intl        long long

#define filein      freopen("input.txt", "r", stdin)

#define fileout     freopen("output.txt", "w", stdout)

#define debug       cout << "YES" << endl

#define what_is(x)  cout << #x << " is " << x << endl

#define pb          push_back

#define pii         pair<int, int>



//find_by_order(int) and order_of_key(int)

//typedef tree < intl , null_type ,less<intl>,rb_tree_tag,tree_order_statistics_node_update > ordered_set;

const int M = 345678;

int k, dist[123456];



int dijkstra()

{

    priority_queue<pii>q; //sum, rem

    for (int i = 0 ; i < k ; i++) {

        dist[i] = 1000000000;

    }

    q.push(mp(0,0));

    dist[0] = 0;

    while( !q.empty() )

    {

        pii a = q.top();

        q.pop();

        int r = a.yy, s = dist[a.yy];

        if( r == 0 && s != 0 ) return s;

        for( int i = 0; i < 2; i++ )

        {

            if( s == 0 && i == 0 ) continue;

            int tr = (r*10 + i)%k;

            if( (tr == 0 && dist[tr] == 0) || dist[tr] > s + i )

            {

                dist[tr] = s+i;

                q.push( mp( -dist[tr], tr ) );

            }

        }

    }

    return dist[0];

}



int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    //filein;

    cin >> k;

    cout << dijkstra() << endl;

    return 0;

}




// Fastest known solution for this problem: