#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
////!pragma
//int f(int k){
//    int rem = 1;
//    vl rems(k);
//    while(rems[rem] == 0){
//        rems[rem] = 1;
//        rem = rem*10%k;
//    }
//    vl ans = rems;
//    int times = 1;
//    while(ans[0] == 0){
//        ++times;
//        vl tmp = FFT_precision::multiply(rems,ans);
//        rep(i,sz(tmp))
//            if(tmp[i] > 0)
//                ans[i%k] = 1;
//    }
//    return times;
//}
//void __(){
//    _(int,k);
//    print f(k);
//}
//
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <vector>
#include <utility>
#include <iostream>
#include <string>
#define pb push_back
#define REP_ZERO_INT(i,r) for(int i = 0; i < r; ++i)
#define GET_REP_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define rep(...) GET_REP_MACRO(__VA_ARGS__,REP_ANY,REP_INT,REP_ZERO_INT)(__VA_ARGS__)
#define all(v) (v).begin(), (v).end()
#define sz(v) ll(v.size())
#define T1 template<typename T> static
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef double ld;
const ll MOD = 1e9 + 7;
T1 ostream& operator<<(ostream& stream, const vector<T>& t);
namespace FFT_precision{
    template<typename T>vector<T> multiply(const vector<T> & a, const vector<T> & b, bool split = false, bool normalize = false);
}
T1 istream& read(T, T, istream& = cin);
namespace FFT_precision{
    typedef double ld; // 'long double' is 2.2 times slower
    struct C { ld re, im;
        C operator * (const C & he) const {
            return C{re * he.re - im * he.im,
                re * he.im + im * he.re};
        }
        void operator += (const C & he) { re += he.re; im += he.im; }
    };
    void dft(vector<C> & a, bool rev) {
        const int n = a.size();
        for(int i = 1, k = 0; i < n; ++i) {
            for(int bit = n / 2; (k ^= bit) < bit; bit /= 2);;;
            if(i < k) swap(a[i], a[k]);
        }
        for(int len = 1, who = 0; len < n; len *= 2, ++who) {
            static vector<C> t[30];
            vector<C> & om = t[who];
            if(om.empty()) {
                om.resize(len);
                const ld ang = 2 * acosl(0) / len;
                rep(i, len) om[i] = i%2 || !who ?
                    C{cos(i*ang), sin(i*ang)} : t[who-1][i/2];
            }
            for(int i = 0; i < n; i += 2 * len)
                rep(k, len) {
                    const C x = a[i+k], y = a[i+k+len]
                        * C{om[k].re, om[k].im * (rev ? -1 : 1)};
                    a[i+k] += y;
                    a[i+k+len] = C{x.re - y.re, x.im - y.im};
                }
        }
        if(rev) rep(i, n) a[i].re /= n;
    }
    template<typename T>vector<T> multiply(const vector<T> & a, const vector<T> & b,
            bool split, bool normalize) {
        if(a.empty() || b.empty()) return {};
        T big = 0; if(normalize) { // [0,B] into [-B/2, B/2]
            assert(a.size() == b.size()); // equal size!!!
            for(T x : a) big = max(big, x);
            for(T x : b) big = max(big, x);
            big /= 2;
        }
        int n = a.size() + b.size();
        vector<T> ans(n - 1);
        /* if(min(a.size(),b.size()) < 190) { // BRUTE FORCE
           rep(i, a.size()) rep(j, b.size()) ans[i+j] += a[i]*b[j];
           return ans; } */
        while(n&(n-1)) ++n;
        auto foo = [&](const vector<C> & w, int i, int k) {
            int j = i ? n - i : 0, r = k ? -1 : 1;
            return C{w[i].re + w[j].re * r, w[i].im
                - w[j].im * r} * (k ? C{0, -0.5} : C{0.5, 0});
        };
        if(!split) { // standard fast version
            vector<C> in(n), done(n);
            rep(i, sz(a)) in[i].re = a[i] - big;
            rep(i, sz(b)) in[i].im = b[i] - big;
            dft(in, false);
            rep(i, n) done[i] = foo(in, i, 0) * foo(in, i, 1);
            dft(done, true);
            rep(i, sz(ans)) ans[i] = is_integral<T>::value ?
                llround(done[i].re) : done[i].re;
            //rep(i,ans.size())err=max(err,abs(done[i].re-ans[i]));
        }
        else { // Split big INTEGERS into pairs a1*M+a2,
            const T M = 1<<15; // where M = sqrt(max_absvalue).
            vector<C> t[2]; // This version is 2.2-2.5 times slower.
            rep(x, 2) {
                t[x].resize(n);
                auto & in = x ? b : a; // below use (in[i]-big) if normalized
                rep(i, sz(in)) t[x][i]=C{ld(in[i]%M), ld(in[i]/M)};
                dft(t[x], false);
            }
            T mul = 1;
            for(int s = 0; s < 3; ++s, mul = (mul*M)%MOD) {
                vector<C> prod(n);
                rep(x, 2) rep(y, 2) if(x + y == s) rep(i, n)
                    prod[i] += foo(t[0], i, x) * foo(t[1], i, y);
                dft(prod, true); // remember: llround(prod[i].re)%MOD*mul !!!
                rep(i, sz(ans)) ans[i]= (ans[i]+llround(prod[i].re)%MOD*mul)%MOD;
            }
        }
        if(normalize) {
            T so_far = 0;
            rep(i, sz(ans)) {
                if(i < (int) a.size()) so_far += a[i] + b[i];
                else so_far -= a[i-a.size()] + b[i-a.size()];
                ans[i] += big * so_far - big * big * min(i + 1, (int) ans.size() - i);
            }
        }
        return ans;
    }
}
struct _print {
    string sep,end;
    bool space;
    ostream &stream;
    _print(string _sep=" ",string _end="\n",
            ostream &_stream = cout)
        : sep(_sep),end(_end),space(false),
            stream(_stream) {}
    ~_print() { stream << end; }
    template <typename T>
        _print &operator , (const T &t) {
            if (space) stream << sep;
            space = true;
            stream << t;
            return *this;
        }
};
#define print _print(),
#define INPUT_WITHOUT_INIT(type,name) type name; cin >> name
#define GET_INPUT_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define _(...) GET_INPUT_MACRO(__VA_ARGS__,_IWI,_IWI,_IWI,_IWI,_IWI,_IWI,INPUT_WITHOUT_INIT)(__VA_ARGS__)
//!pragma
int f(int k){
    int rem = 1;
    vl rems(k);
    while(rems[rem] == 0){
        rems[rem] = 1;
        rem = rem*10%k;
    }
    vl ans = rems;
    int times = 1;
    while(ans[0] == 0){
        ++times;
        vl tmp = FFT_precision::multiply(rems,ans);
        rep(i,sz(tmp))
            if(tmp[i] > 0)
                ans[i%k] = 1;
    }
    return times;
}
void __(){
    _(int,k);
    print f(k);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
        __();
}

Measured memory_bytes: 15848