#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

using base = complex<double>;
const int MAXN = 1 << 18;
base _a[MAXN], _b[MAXN], _c[MAXN];
namespace fft {
    int rev[MAXN];
    base wlen_pw[MAXN];
    
    void fft (base a[], int n, bool invert) {
        for (int i = 0; i < n; ++i)
            if (i < rev[i])
                swap(a[i], a[rev[i]]);
    
        for (int len = 2; len <= n; len <<= 1) {
            double ang = 2 * M_PI / len * (invert ? -1 : 1);
            int len2 = len >> 1;
    
            base wlen(cos(ang), sin(ang));
            wlen_pw[0] = base(1, 0);
            for (int i = 1; i < len2; ++i)
                wlen_pw[i] = wlen_pw[i - 1] * wlen;
    
            for (int i = 0; i < n; i += len) {
                base t,
                    *pu = a + i,
                    *pv = a + i + len2, 
                    *pu_end = a + i + len2,
                    *pw = wlen_pw;
                for (; pu != pu_end; ++pu, ++pv, ++pw) {
                    t = *pv * *pw;
                    *pv = *pu - t;
                    *pu += t;
                }
            }
        }
    
        if (invert)
            for (int i = 0; i < n; ++i)
                a[i] /= n;
    }
    
    void calc_rev (int n) {
        int lg = 1;
        while ((1 << lg) < n) ++lg;
        for (int i = 0; i < n; ++i) {
            rev[i] = 0;
            for (int j = 0; j < lg; ++j)
                if (i & (1 << j))
                    rev[i] |= 1 << (lg - 1 - j);
        }
    }

    vector<int> multiply(vector<int> a, vector<int> b) {
        int n = 1;
        while (n < max(a.size(), b.size()))
            n *= 2;
        n *= 2;
        calc_rev(n);
        for (int i = 0; i < n; ++i)
            _a[i] = 0, _b[i] = 0;
        for (int i = 0; i < (int)a.size(); ++i)
            _a[i] = a[i];
        for (int i = 0; i < (int)b.size(); ++i)
            _b[i] = b[i];
        fft(_a, n, false);
        fft(_b, n, false);
        for (int i = 0; i < n; ++i)
            _c[i] = _a[i] * _b[i];
        fft(_c, n, true);
        vector<int> ans(n);
        for (int i = 0; i < n; ++i)
            ans[i] = int(_c[i].real() + 0.5);
        return ans;
    }
}
using fft::multiply;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    int n;
    cin >> n;
    /*
    int mn = INF;
    for (ll x = n; x < 1000000ll * n; x += n)
        setmin(mn, sum(x));
    int x = 1;
    forn(_, 0, 1000000) {
        x *= 10;
        x %= n;
        if (x == 0) {
            cout << 1 << '\n';
            return 0;
        }
        setmin(mn, 1 + n - x);
    }
    cout << mn << '\n';
    */
    vector<int> a(n);
    int x = 1;
    while (!a[x]) {
        a[x] = 1;
        x *= 10;
        x %= n;
    }
    ++a[0];
    vector<vector<int>> pw(6);
    pw[0] = a;
    forn(i, 1, 6) {
        pw[i] = multiply(pw[i - 1], pw[i - 1]);
        int sz = pw[i].size();
        forn(j, n, sz)
            if (pw[i][j])
                ++pw[i][j - n];
        pw[i].resize(n);
        forn(j, 1, n) if (pw[i][j]) pw[i][j] = 1;
        if (pw[i][0] > 2) pw[i][0] = 2;
    }
    int ans = 0, k = -1;
    vector<int> tmp;
    ford(i, 0, 6) if (pw[i][0] <= 1) {
        ans = 1 << i;
        k = i - 1;
        tmp = pw[i];
        break;
    }
    while (k >= 0) {
        vector<int> test = multiply(tmp, pw[k]);
        int sz = test.size();
        forn(j, n, sz) if (test[j]) ++test[j - n];
        test.resize(n);
        forn(j, 1, n) if (test[j]) test[j] = 1;
        if (test[0] > 2) test[0] = 2;
        if (test[0] <= 1) {
            tmp = test;
            ans += 1 << k;
        }
        --k;
    }
    cout << ans + 1 << '\n';
}


Measured memory_bytes: 25776