import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

immutable inf = 10^^6;

void main() {
    int k;
    scan(k);

    auto d = new int[](k);
    d[] = inf;
    d[1] = 1;

    auto deq = Deque!(int)(3*k);
    deq.pushBack(1);

    while (!deq.empty) {
        auto u = deq.front;
        deq.popFront();

        if (d[(u + 1) % k] > d[u] + 1) {
            d[(u + 1) % k] = d[u] + 1;
            deq.pushBack((u + 1) % k);
        }

        if (d[(u * 10) % k] > d[u]) {
            d[(u * 10) % k] = d[u];
            deq.pushFront((u * 10) % k);
        }
    }

    writeln(d[0]);
}

struct Deque(T) {
    private {
        int N, head, tail;
        T[] deq;
    }

    this(int n) {
        N = n + 1;
        deq = new T[](N + 1);
    }

    bool empty() {
        return head == tail;
    }

    bool full() {
        return head == ((tail + 1) % N);
    }

    int length() {
        return (tail - head + N) % N;
    }

    T front() {
        assert(!empty);
        return deq[head];
    }

    T back() {
        assert(!empty);
        return deq[(tail - 1 + N) % N];
    }

    void pushFront(T x) {
        assert(!full);
        head = (head - 1 + N) % N;
        deq[head] = x;
    }

    void pushBack(T x) {
        assert(!full);
        deq[tail++] = x;
        tail %= N;
    }

    void popFront() {
        assert(!empty);
        head = (head + 1) % N;
    }

    void popBack() {
        assert(!empty);
        tail = (tail - 1 + N) % N;
    }
}

unittest {
    int n = 5;
    auto deq = Deque!(int)(n);

    deq.pushFront(3);
    deq.pushBack(1);
    deq.pushBack(4);
    deq.pushFront(5);

    assert(deq.front == 5);
    assert(deq.back == 4);
    assert(deq.length == 4);

    deq.pushFront(0);

    assert(deq.full);
    assert(deq.front == 0);
    assert(deq.length == 5);

    deq.popFront();
    deq.popFront();
    deq.popBack();

    assert(deq.front == 3);
    assert(deq.back == 1);
    assert(deq.length == 2);

    deq.popBack();
    deq.popFront();

    assert(deq.empty);
    assert(deq.length == 0);

    writeln("ok");
}

void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}