#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
using namespace std;

struct node {
    int idx, cost;
    node () {}
    node(int _idx, int _cost) {
        idx = _idx;
        cost = _cost;
    }
    bool operator < (const node &t) const {
        return cost > t.cost;
    }
};
int main() {
    int K;
    cin >> K;
    vector<int> dist(K + 1, 2e9);

    priority_queue<node> pq;
    pq.push(node(K, 0));
    while(!pq.empty()) {
        node c = pq.top();
        pq.pop();

        for(int i = 0; i <= 9; ++i) {
            if(i == 0 and c.idx == K) continue;
            int next_number = (c.idx * 10 + i) % K;
            if(i + c.cost < dist[next_number]) {
                dist[next_number] = i + c.cost;
                pq.push(node(next_number, c.cost + i));
            }
        }
    }
    cout << dist[0] << endl;
    return 0;
}