#include <cstdio>
#include <queue>
#include <cstdlib>
#include <cstring> 
#define Max(A, B) A > B ? A : B 
#define Reg register
namespace Quick_In {
    char b[1<<15],*s = b,*t = b;
    #define GetC() (s == t && (t = (s = b) + fread(b, 1, 1 << 15, stdin), s == t) ? 0 : *s++)
    int Read() {
        Reg char C; Reg int A;
        while(C = GetC(),(C < '0' || C > '9'));
        A = C - '0';
        while(C = GetC(),C >= '0' && C <= '9')  A = (A << 3) + (A << 1) + C - '0';
        return A;
    }
}
using namespace Quick_In;
typedef long long LL;
std::queue<LL> Queue;
const LL MaxN = 1e7 + 10;
const LL Inf = 214748364;
LL N, K, M, X, Y;
LL Dis[MaxN * 2];
struct Edge {
    LL To, Next, Val;
}Road[MaxN];
LL Cnt = 0, Last[MaxN];
void Add(LL U, LL V, LL Val) {
    Road[++Cnt] = (Edge){V, Last[U], Val}, Last[U] = Cnt;
}
bool InQueue[MaxN];
LL Count[MaxN];
LL Spfa(int Now) {
    for(LL i = 0; i < MaxN; i++) Dis[i] = Inf, InQueue[i] = false;
    Queue.push(Now); InQueue[Now] = 1; Dis[Now] = 0;
    while(!Queue.empty()) {
        LL Top = Queue.front(); 
        for(LL i = Last[Top]; i; i = Road[i].Next) {
            LL To = Road[i].To;
            if(Dis[Top] + Road[i].Val < Dis[To]) {
                Dis[To] = Dis[Top] + Road[i].Val;
                if(!InQueue[To]) {                 
                    Queue.push(To);
                    InQueue[To] = true;
                } 
            }
        }
        Queue.pop(); InQueue[Top] = false; 
    }	
}
int main() {
    //N = Read(); 
    scanf("%lld", &N);
    for(int i = 0; i < N; i++)  
            Add(i, (i + 1) % N, 1),
            Add(i, (i * 10) % N, 0); 
    Spfa(1);
    printf("%lld", Dis[0] + 1); 
} 