#include <iostream>
#include <deque>
using namespace std;int d[100005];int main(){int k;cin>>k;deque<int> q;for(int i=0;i<k;i++) d[i]=1e9;d[1]=1;q.push_front(1);while(!q.empty()){int l=q.front();q.pop_front();if(d[l*10%k]>d[l]){d[l*10%k]=d[l];q.push_front(l*10%k);}if(d[(l+1)%k]>d[l]+1){d[(l+1)%k]=d[l]+1;q.push_back((l+1)%k);}}cout<<d[0];}