// Original C++ solution (slower):
/*

 * 很神奇的一道题目

 * 求出k的倍数的正数x，使得x的位数和最小。

 * eg k = 6 x = 12(位数和为3) x = 30(位数和为3)

 * 

 * 考虑正数x 其变为 x+1 需要代价1.

 *    正数x 变成 x*10 需要代价0.

 * 由于我们只需要得到k的倍数，也就是说在 %k 意义下为0的点。

 * 所以只有[0,k-1]k点。对每个点建立两条边，分别为(x+1)%k 和 (x*10)%k

 */

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

const int inf = 0x3f3f3f3f;

struct Edge {

    int to,val;

    Edge(){}

    Edge(int _t,int _v){to = _t;val = _v;}

};

struct qNode {

    int u,val;

    qNode(){}

    qNode(int _u,int _v) {u = _u;val = _v;}

    bool operator < (const qNode &a) const{

        return val > a.val;

    }

};

vector<Edge> ways[maxn];

int dist[maxn];

bool vis[maxn];

int n;

inline void init() {

    for(int i=0;i<maxn;i++) ways[i].clear();

    memset(vis,0,sizeof(vis));

    memset(dist,inf,sizeof(dist));

}

inline void addedge(int from,int to,int val) {

    ways[from].push_back(Edge(to,val));

}

int solve(int from,int to) {

    priority_queue<qNode> qu;

    dist[from] = 1;

    qu.push(qNode(from,1));

    qNode now;

    while(!qu.empty()) {

        now = qu.top();qu.pop();

        int u = now.u;

        if(vis[u]) continue;

        vis[u] = true;

        for(auto tmp:ways[u]) {

            int v = tmp.to,cost = tmp.val;

            if(!vis[v] && dist[v] > dist[u]+cost) {

                dist[v] = dist[u] + cost;

                qu.push(qNode(v,dist[v]));

            }

        }

    }

    return dist[to];

}

int main()

{

    while(~scanf("%d",&n)){

        init();

        for(int i=1;i<n;i++) {

            addedge(i,(i+1)%n,1);

            addedge(i,(i*10)%n,0);

        }

        int ans = solve(1,0);

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

    }

    return 0;

}

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

//#pragma GCC optimize(3)



#define X first

#define Y second

#define PB push_back

#define MP make_pair

#define mset(var,val) memset(var,val,sizeof(var))

#define IOS ios::sync_with_stdio(false);cin.tie(0)



#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)

#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)

#define rep(i,n) for(int i = 0; i < n; ++i)

#define rep1(i,n) for(int i = 1; i <= n; ++i)



using namespace std;

typedef long long ll;



namespace debug {

#ifdef local

#define dbg(args...) do { cout << #args << " -> "; err(args); } while (0)

#else

#define dbg(...)

#endif

void err() {

    cout << endl;

}

template<template<typename...> class T, typename t, typename... Args>

void err(T<t> a, Args... args) {

    for (auto x: a)

        cout << x << ' ';

    err(args...);

}

template<typename T, typename... Args>

void err(T a, Args... args) {

    cout << a << ' ';

    err(args...);

}

}



namespace stdio_input {

#define scd(args...) do{scanf_int(args);} while(0)

void scanf_int() {}

template<typename T, typename... Args>

void scanf_int(T &a, Args&... args) {

    scanf("%d", &a);

    scanf_int(args...);

}

#define scl(args...) do{scanf_ll(args);} while(0)

void scanf_ll() {}

template<typename T, typename... Args>

void scanf_ll(T &a, Args&... args) {

    scanf("%lld", &a);

    scanf_ll(args...);

}

#define scf(args...) do{scanf_double(args);} while(0)

void scanf_double() {}

template<typename T, typename... Args>

void scanf_double(T &a, Args&... args) {

    scanf("%lf", &a);

    scanf_double(args...);

}

}



namespace const_var {

const int inf = 0x3f3f3f3f;

const long long INF = 0x3f3f3f3f3f3f3f3fLL;

const double PI = acos(-1.0);

const int N = 1e5+10;

const long double eps = 1e-20;

const int mod = 1e9+7;

}



using namespace debug;

using namespace stdio_input;

using namespace const_var;



int T = 0;

void testcase() {

    cout << "Case #" << (++T) << ": ";

}



int dis[N];

bool vis[N];



struct P{

    int u, w;

    bool operator < (const P & b) const {

        return w > b.w;

    }

};



priority_queue<P> q;

void work() {

    int k;

    cin >> k;

    mset(dis, inf);

    dis[1] = 1;

    q.push({1,1});

    while(!q.empty()){

        int u = q.top().u;

        int w = q.top().w;

        q.pop();

        if(u == 0) break;

        if(vis[u] || dis[u] != w) continue;

        vis[u] = true;

        int v = u * 10 % k;

        if(dis[u] < dis[v]){

            dis[v] = dis[u];

            q.push({v, dis[v]});

        }

        v = (u + 1) % k;

        if(dis[u] + 1 < dis[v]){

            dis[v] = dis[u] + 1;

            q.push({v, dis[v]});

        }

    }

    cout << dis[0] << endl;

}



int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.sql","w",stdout);

#endif // local

    IOS;

//    getPrime();

//    init();

    int t;

//    cin >> t;

//    cin.get();

//    for(;t--;)

    work();

    return 0;

}


// Fastest known solution for this problem: