import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

int[2][10^^5] GP;
bool[10^^5] MS;

void main()
{
    auto K = readln.chomp.to!int;

    foreach (i; 1..K) {
        GP[i][0] = (i*10)%K;
        GP[i][1] = (i+1)%K;
    }

    auto ss = [[1, 1]];
    for (;;) {
        auto h = ss[0];
        auto i = h[0];
        auto c = h[1];
        if (!i) break;
        ss = ss[1..$];
        if (MS[i]) continue;
        MS[i] = true;

        auto n = GP[i];
        ss = [[n[0], c]] ~ ss ~ [n[1], c+1];
    }

    writeln(ss[0][1]);
}