var lines = [];
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {
    var K = Number(lines[0]);

    var cost = Array(K).fill(Infinity).map(i => i = Array(K).fill(Infinity))
    var d = Array(K).fill(Infinity)
    var used = Array(K).fill(false)

    for (var i = 0; i < K; i++) {
        cost[i][(i + 1) % K] = 1;
        cost[i][(i * 10) % K] = 0;
        cost[i][i] = 0;
    }

    // ダイクストラ法(O(N^2))
    d[1] = 0;

    while (1) {
        var v = -1;
        for (var i = 0; i < K; i++) {
            if (!used[i] && (v === -1 || d[i] < d[v])) { v = i }
        }

        if (v === -1) { break; }
        used[v] = true;

        for (var i = 0; i < K; i++) {
            if (d[v] + cost[v][i] < d[i]) { d[i] = d[v] + cost[v][i]; }
        }
    }

    console.log(d[0] + 1)
});