#include <bits/stdc++.h>

using namespace std;

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//
//using namespace __gnu_pbds;
//template<typename dtype> using ordered_set = tree<dtype, null_type, less<dtype>, rb_tree_tag, tree_order_statistics_node_update>;

class Timer {
    clock_t start;
    string name;
public:
    Timer() {name = "";start = clock();}
    Timer(string s){name = s;start = clock();}
    ~Timer() {fprintf(stderr, "%s: %.3gs\n", name.c_str(), 1.0*(clock() - start) / CLOCKS_PER_SEC);}
};

//#define isValid(a, b) (a >= 0 && a < b)
//int dr[]  =  {0, -1, -1, -1,  0,  1, 1, 1};
//int dc[]  =  {1,  1,  0, -1, -1, -1, 0, 1};

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define what_is(x) cerr << fixed << setprecision(2) << boolalpha << #x << " = " << x << endl

const double EPS = 1e-9;
const long double PI = acos(-1.0L);

template<typename dtype> inline dtype sq(dtype a){return a*a;}
template<typename dtype1, typename dtype2> inline pair<dtype1, dtype2> mp(dtype1 a, dtype2 b){return make_pair(a, b);}
template<typename dtype1, typename dtype2> inline dtype1 safeMod(dtype1 a, dtype2 m){return (a%m + m)%m;}/*handling negative sign of remainder*/
template<typename dtype1, typename dtype2> inline bool isEq(dtype1 a, dtype2 b){return abs(a - b) < EPS;}
template<typename dtype1, typename dtype2, typename dtype3> inline bool isEq(dtype1 a, dtype2 b, dtype3 eps){return abs(a - b) < eps;}
template<typename dtype> inline dtype toRad(dtype deg){return deg*PI/180.0;}
template<typename dtype> inline dtype toDeg(dtype rad){return rad*180.0/PI;}
template<typename dtype> inline bool isKthBitOn(dtype n, int k){assert(n <= numeric_limits<dtype>::max());assert(k<=numeric_limits<dtype>::digits);dtype ONE = 1;return bool((n & (ONE<<k)));}
template<typename dtype> inline void setKthBit(dtype& n, int k){assert(n <= numeric_limits<dtype>::max());assert(k<=numeric_limits<dtype>::digits);dtype ONE = 1;n = (n|(ONE<<k));}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int oo = 0x3f3f3f3f;
const int MAX = 200010;
const int MOD = 1000000007;
const int precision = 10;
int k;
bool vis[300][100005];
int zero_one_bfs()
{
    deque<pii>dq;
    pii u(1, 1);
    dq.push_back(u);
    vis[1][1] = true;
    int s;
    ll n;
    pii v;
    while(!dq.empty()){
        u = dq.front();
        dq.pop_front();
        tie(s, n) = u;
        if(n%k == 0)
            return s;
        v = pii(s + 1, (n+1)%k);
        if(!vis[v.first][v.second]){
            vis[v.first][v.second] = true;
            dq.push_back(v);//edge with cost 1
        }
        v = pii(s, (n*10)%k);
        if(!vis[v.first][v.second]){
            vis[v.first][v.second] = true;
            dq.push_front(v);//edge with cost 0
        }
    }
    return -1;
}
int main(int argc, char* argv[])
{
    #ifdef NAbdulla
    //assert(freopen("in.txt", "r", stdin));
    //assert(freopen("out.txt", "w", stdout));
    #endif // NAbdulla
    //ios_base::sync_with_stdio(false); cin.tie(NULL);
    //cout << fixed << setprecision(precision);
    scanf("%d", &k);
    printf("%d", zero_one_bfs());
    return 0;
}


Measured memory_bytes: 5888