import core.bitop;
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.random;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
  int k = readln.chomp.to!int;
  int[] done = new int[](k);
  done[] = int.max;
  done[1] = 1;
  int[] queue = [1];
  while (queue.length)
  {
    int node = queue.front;
    queue = queue[1 .. $];
    int next10 = (node * 10) % k;
    if (done[node] < done[next10])
    {
      done[next10] = done[node];
      queue = next10 ~ queue;
    }
    int next1 = (node + 1) % k;
    if (done[node] + 1 < done[next1]) {
      done[next1] = done[node] + 1;
      queue ~= next1;
    }
  }
  done[0].writeln;
}
