stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

#define FOR(i,a,b) for(int i = int(a); i < int(b); i++)

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.3641342898390967x):
//#include<bits/stdc++.h>

#include<iostream>

#include<cstring>

#include<deque>

#include<string>

#define mst(a,b) memset(a,b,sizeof(a))

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

const int maxn = 2e5+50;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

int dis[maxn];

bool vis[maxn];

deque<int>qu;



int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

#endif

//freopen("G.IN","r",stdin);

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int k;cin>>k;

    mst(dis,0x3f);

    qu.push_back(1);dis[1]=1;

    for(;!qu.empty();){

        int a=qu.front();qu.pop_front();

        if(vis[a])continue;

        int g=(a*10)%k;

        if(!vis[g] and dis[a]<dis[g]){

            dis[g]=dis[a];

            qu.push_front(g);

        }

        g=(a+1)%k;

        if(!vis[g] and dis[a]+1<dis[g]){

            dis[g]=dis[a]+1;

            qu.push_back(g);

        }

    }

    cout<<dis[0];

    return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

#define FOR(i,a,b) for(int i = int(a); i < int(b); i++)

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.05250853364266x):
#include <bits/stdc++.h>

#include <ext/rope>

using namespace __gnu_cxx;

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

#define ALL(x) x.begin(),x.end()

#define pii pair<int, int>

#define debug(a) cout << #a": " << a << endl;

#define eularMod(a, b) a < b ? a : a % b + b

inline int lowbit(int x){ return x & -x; }

typedef long long LL;

typedef unsigned long long ULL;

const int N = 1e5 + 10;

const int mod = (int) 1e9 + 7;

const int INF = 0x3f3f3f3f;

const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

const double PI = acos(-1.0);

const double eps = 1e-6;



int k;

int dis[N];

bool inq[N];



int cal(int x) {

    int res = 0;



    for (; x; x /= 10)

        res += x % 10;



    return res;

}



queue<int> Q;



void spfa() {

    mst(dis, 0x3f);



    dis[1] = 1;

    inq[1] = true;



    Q.push(1);



    for (;!Q.empty();) {

        int u = Q.front();

        Q.pop();



        inq[u] = false;



        int v = (u + 1) % k;



        if (dis[v] > dis[u] + 1) {

            dis[v] = dis[u] + 1;



            if (!inq[v])

                Q.push(v);

        }



        v = (u * 10) % k;



        if (dis[v] > dis[u]) {

            dis[v] = dis[u];



            if (!inq[v])

                Q.push(v);

        }

    }

}



int main() {

#ifdef purple_bro

    freopen("in.txt", "r", stdin);

//    freopen("out.txt","w",stdout);

#endif

    scanf("%d", &k);



    spfa();



    printf("%d\n", dis[0]);

    return 0;

}
// Slower C++ solution:
//#include<bits/stdc++.h>

#include<iostream>

#include<cstring>

#include<deque>

#include<string>

#define mst(a,b) memset(a,b,sizeof(a))

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

const int maxn = 2e5+50;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

int dis[maxn];

bool vis[maxn];

deque<int>qu;



int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

#endif

//freopen("G.IN","r",stdin);

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int k;cin>>k;

    mst(dis,0x3f);

    qu.push_back(1);dis[1]=1;

    for(;!qu.empty();){

        int a=qu.front();qu.pop_front();

        if(vis[a])continue;

        int g=(a*10)%k;

        if(!vis[g] and dis[a]<dis[g]){

            dis[g]=dis[a];

            qu.push_front(g);

        }

        g=(a+1)%k;

        if(!vis[g] and dis[a]+1<dis[g]){

            dis[g]=dis[a]+1;

            qu.push_back(g);

        }

    }

    cout<<dis[0];

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.208951160391396x):
#include <bits/stdc++.h>

#include <ext/rope>

using namespace __gnu_cxx;

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

#define ALL(x) x.begin(),x.end()

#define pii pair<int, int>

#define debug(a) cout << #a": " << a << endl;

#define eularMod(a, b) a < b ? a : a % b + b

inline int lowbit(int x){ return x & -x; }

typedef long long LL;

typedef unsigned long long ULL;

const int N = 1e5 + 10;

const int mod = (int) 1e9 + 7;

const int INF = 0x3f3f3f3f;

const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

const double PI = acos(-1.0);

const double eps = 1e-6;



int k;

int dis[N];

bool inq[N];



int cal(int x) {

    int res = 0;



    for (; x; x /= 10)

        res += x % 10;



    return res;

}



queue<int> Q;



void spfa() {

    mst(dis, 0x3f);



    dis[1] = 1;

    inq[1] = true;



    Q.push(1);



    for (;!Q.empty();) {

        int u = Q.front();

        Q.pop();



        inq[u] = false;



        int v = (u + 1) % k;



        if (dis[v] > dis[u] + 1) {

            dis[v] = dis[u] + 1;



            if (!inq[v])

                Q.push(v);

        }



        v = (u * 10) % k;



        if (dis[v] > dis[u]) {

            dis[v] = dis[u];



            if (!inq[v])

                Q.push(v);

        }

    }

}



int main() {

#ifdef purple_bro

    freopen("in.txt", "r", stdin);

//    freopen("out.txt","w",stdout);

#endif

    scanf("%d", &k);



    spfa();



    printf("%d\n", dis[0]);

    return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

#define FOR(i,a,b) for(int i = int(a); i < int(b); i++)

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.139826091778554x):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

	for(int i = 1;i <= k;i++)

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define F(i,a,b) for(int i=a;i<=(b);++i)

#define ll long long

int k,a[100001],vis[100001];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

int c[100001];

int main(){

	scanf("%d",&k);

	memset(a,0x3f,sizeof a);

	a[1]=1; pq.push(make_pair(1,1));

	while(!pq.empty()){

		pair<int,int> P=pq.top(); pq.pop();

		int u=P.second, d=P.first;

		if(vis[u]) continue;

		int v=(u+1)%k;

		if(a[v]>d+1) a[v]=d+1, pq.push(make_pair(a[v],v));

		for(int i=u;;i=i*10%k){

			if(c[i]||vis[i]) break;

			if(a[i]>d) a[i]=d, pq.push(make_pair(a[i],i));

			c[i]=1;

		}

		for(int i=u;;i=i*10%k){

			if(!c[i]) break;

			c[i]=0;

		}

		vis[u]=1;

	} printf("%d",a[0]);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6938561425416614x):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

	for(int i = 1;i <= k;i++)

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

int k,cnt=0,h[100005],dis[100005];

struct Edge{

	int to,next,w;

}e[400005];

queue<int> q;

inline void add(int u,int v,int w){

	e[++cnt].to=v;

	e[cnt].next=h[u];

	e[cnt].w=w;

	h[u]=cnt;

}

inline void init(){

	scanf("%d",&k);

	for(int i=0;i<k-1;i++){

		add(i,i*10%k,0);

		add(i,i+1,1);

	}

	add(k-1,(k-1)*10%k,0);

	add(k-1,0,1);

	memset(dis,127/3,sizeof(dis));

	dis[1]=0;

}

int main(){

	init();

	q.push(1);

	while(!q.empty()){

		int x=q.front();

		q.pop();

		for(int i=h[x];i;i=e[i].next)

			if(dis[e[i].to]>dis[x]+e[i].w){

				dis[e[i].to]=dis[x]+e[i].w;

				q.push(e[i].to);

			}

	}

	printf("%d\n",dis[0]+1);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.2890355445501978x):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

	for(int i = 1;i <= k;i++)

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}
// Slower C++ solution:
//#include<bits/stdc++.h>

#include<iostream>

#include<cstring>

#include<deque>

#include<string>

#define mst(a,b) memset(a,b,sizeof(a))

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

const int maxn = 2e5+50;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

int dis[maxn];

bool vis[maxn];

deque<int>qu;



int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

#endif

//freopen("G.IN","r",stdin);

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int k;cin>>k;

    mst(dis,0x3f);

    qu.push_back(1);dis[1]=1;

    for(;!qu.empty();){

        int a=qu.front();qu.pop_front();

        if(vis[a])continue;

        int g=(a*10)%k;

        if(!vis[g] and dis[a]<dis[g]){

            dis[g]=dis[a];

            qu.push_front(g);

        }

        g=(a+1)%k;

        if(!vis[g] and dis[a]+1<dis[g]){

            dis[g]=dis[a]+1;

            qu.push_back(g);

        }

    }

    cout<<dis[0];

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.434389278577248x):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

	for(int i = 1;i <= k;i++)

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#include <ext/rope>

using namespace __gnu_cxx;

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

#define ALL(x) x.begin(),x.end()

#define pii pair<int, int>

#define debug(a) cout << #a": " << a << endl;

#define eularMod(a, b) a < b ? a : a % b + b

inline int lowbit(int x){ return x & -x; }

typedef long long LL;

typedef unsigned long long ULL;

const int N = 1e5 + 10;

const int mod = (int) 1e9 + 7;

const int INF = 0x3f3f3f3f;

const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

const double PI = acos(-1.0);

const double eps = 1e-6;



int k;

int dis[N];

bool inq[N];



int cal(int x) {

    int res = 0;



    for (; x; x /= 10)

        res += x % 10;



    return res;

}



queue<int> Q;



void spfa() {

    mst(dis, 0x3f);



    dis[1] = 1;

    inq[1] = true;



    Q.push(1);



    for (;!Q.empty();) {

        int u = Q.front();

        Q.pop();



        inq[u] = false;



        int v = (u + 1) % k;



        if (dis[v] > dis[u] + 1) {

            dis[v] = dis[u] + 1;



            if (!inq[v])

                Q.push(v);

        }



        v = (u * 10) % k;



        if (dis[v] > dis[u]) {

            dis[v] = dis[u];



            if (!inq[v])

                Q.push(v);

        }

    }

}



int main() {

#ifdef purple_bro

    freopen("in.txt", "r", stdin);

//    freopen("out.txt","w",stdout);

#endif

    scanf("%d", &k);



    spfa();



    printf("%d\n", dis[0]);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1864741319350458x):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

	for(int i = 1;i <= k;i++)

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

#define FOR(i,a,b) for(int i = int(a); i < int(b); i++)

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.018203401326681x):
#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define ll long long

#define linf 0x3f3f3f3f3f3f3f3fLL

using namespace std;

const int N = 1e5+5;

const ll mod = 1e9+7;

const ll INF = 1e18;

int head[N];

int ne;

struct edge{

	int to,nt,w;

}e[500004];

queue<int>q;

int dis[100004];

void spfa()

{

	memset(dis,127/3,sizeof(dis));

	dis[1]=0;

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=head[x];i;i=e[i].nt){

			if( dis[e[i].to]>dis[x]+e[i].w){

				dis[e[i].to]=dis[x]+e[i].w;

				q.push(e[i].to);

			}

		}

	}

}

void add(int u,int v,int w){

	 e[++ne].to = v;e[ne].nt = head[u];

	 e[ne].w=w;

	 head[u]=ne;

}

 

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)

	{

		add(i,(i+1)%n,1);

		add(i,(i*10)%n,0);

	}

	q.push(1);

	spfa();

	printf("%d\n",dis[0]+1);

 

	return 0;

}
// Slower C++ solution:
//#include<bits/stdc++.h>

#include<iostream>

#include<cstring>

#include<deque>

#include<string>

#define mst(a,b) memset(a,b,sizeof(a))

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

const int maxn = 2e5+50;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

int dis[maxn];

bool vis[maxn];

deque<int>qu;



int main() {

#ifdef local

    freopen("in.txt","r",stdin);

//    freopen("out.txt","w",stdout);

#endif

//freopen("G.IN","r",stdin);

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int k;cin>>k;

    mst(dis,0x3f);

    qu.push_back(1);dis[1]=1;

    for(;!qu.empty();){

        int a=qu.front();qu.pop_front();

        if(vis[a])continue;

        int g=(a*10)%k;

        if(!vis[g] and dis[a]<dis[g]){

            dis[g]=dis[a];

            qu.push_front(g);

        }

        g=(a+1)%k;

        if(!vis[g] and dis[a]+1<dis[g]){

            dis[g]=dis[a]+1;

            qu.push_back(g);

        }

    }

    cout<<dis[0];

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.101945519010678x):
#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define ll long long

#define linf 0x3f3f3f3f3f3f3f3fLL

using namespace std;

const int N = 1e5+5;

const ll mod = 1e9+7;

const ll INF = 1e18;

int head[N];

int ne;

struct edge{

	int to,nt,w;

}e[500004];

queue<int>q;

int dis[100004];

void spfa()

{

	memset(dis,127/3,sizeof(dis));

	dis[1]=0;

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=head[x];i;i=e[i].nt){

			if( dis[e[i].to]>dis[x]+e[i].w){

				dis[e[i].to]=dis[x]+e[i].w;

				q.push(e[i].to);

			}

		}

	}

}

void add(int u,int v,int w){

	 e[++ne].to = v;e[ne].nt = head[u];

	 e[ne].w=w;

	 head[u]=ne;

}

 

int main()

{

	int n;

	scanf("%d",&n);

	for(int i=0;i<n;i++)

	{

		add(i,(i+1)%n,1);

		add(i,(i*10)%n,0);

	}

	q.push(1);

	spfa();

	printf("%d\n",dis[0]+1);

 

	return 0;

}