stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

Problem : atcoder 084D

Algorithm : dijkstra

Status :

*/

#include <bits/stdc++.h>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5;



int n,len;

int head[MAXN],dis[MAXN],vis[MAXN];

priority_queue<pii,vector<pii>,greater<pii> > q;



struct Edge{

	int to,next,w;

} e[MAXN * 2];



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

	e[++len].to = v;

	e[len].next = head[u];

	e[len].w = w;

	head[u] = len;

}



int main(){

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

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

    memset(head,-1,sizeof(head));

	scanf("%d",&n);

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

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

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

		dis[i] = INF;

	}

	dis[1] = 1;

	q.push(make_pair(0,1));

	while(!q.empty()){

		int u = q.top().second;

		q.pop();

		if(vis[u])

		    continue;

		vis[u] = true;

		for(int i = head[u];i != -1;i = e[i].next){

			int v = e[i].to;

			if(dis[v] > dis[u] + e[i].w){

				dis[v] = dis[u] + e[i].w;

				q.push(make_pair(dis[v],v));

			}

		}

	}

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

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.444084936912333x):
#include <cstdio>

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#define INF 1000000000

#define M 1000005

using namespace std;

int k,nxt[M],head[M],to[M],adj[M],dist[M],tot;

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

	nxt[++tot]=head[u];head[u]=tot;to[tot]=v;adj[tot]=w;

	return;

}

struct node{

	int dis,id;

	bool operator< (const node b) const{return dis<b.dis;}

	bool operator> (const node b) const{return dis>b.dis;}

};

int dijkstra(){

	priority_queue <node,vector<node>,greater<node> > Q;

	for (register int i=1;i<=k;i++) dist[i]=INF;

	dist[2]=1;Q.push((node){1,2});

	while (!Q.empty()){

		node now=Q.top();Q.pop();

		if (now.dis!=dist[now.id]) continue;

		for (register int i=head[now.id];i;i=nxt[i])

			if (dist[to[i]]>now.dis+adj[i]){

				dist[to[i]]=now.dis+adj[i];

				Q.push((node){dist[to[i]],to[i]});

			}

	}

	return dist[1];

}

int main(){

	scanf("%d",&k);

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

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

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

	}

	printf("%d",dijkstra());

	return 0;

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

using namespace std;

const int N=1e5+7;

const int INF=0x3f;

int m,n,k,p,cnt;

int dis[N],head[N];

struct edge

{

    int nx,to,dist;

} e[N*40];

void add_edge(int a,int b,int dist)

{

    cnt++;e[cnt].nx=head[a];e[cnt].to=b;e[cnt].dist=dist;head[a]=cnt;

}

struct node

{

    int pos,dist;

    bool operator<(const node &x) const

    {

        return x.dist<dist;

    }

};

priority_queue<node> que;

bool vis[N];

void dijkstra(int pos)

{

    for (int i=1;i<=N;i++) dis[i]=INF;

    que.push((node){pos,0});dis[pos]=0;

    while (!que.empty())

    {

        node tmp=que.top();que.pop();

        int x=tmp.pos;

        if (vis[x]) continue;

        vis[x]=true;

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

        {

            int y=e[i].to;

            if (dis[y]>dis[x]+e[i].dist)

            {

                dis[y]=dis[x]+e[i].dist;

                if  (!vis[y]) que.push((node) {y,dis[y]});

            }

        }

    }

}

int main()

{

	scanf("%d",&n);

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

	{

		for (int j=0;j<=9;j++)

		add_edge(i,((i-1)*10+j)%n+1,j);

	}

	for (int j=1;j<=9;j++) add_edge(0,j+1,j);

	dijkstra(0);

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

	return 0;

}

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

using namespace std;

deque<pair<int,int> > p;

bool flag[100000001];

int l;

void suanfa(){

    while(p.size()) {

        pair<int,int> 

		now=p.front(); 

		p.pop_front();

        if(flag[now.first]) 

		    continue;

        flag[now.first]=true;

        if(!now.first){

            cout<<now.second<<endl;

            return;

        }

        p.push_front(make_pair(now.first*10%l,now.second));

        p.push_back(make_pair((now.first+1)%l,now.second+1));

    }

}

int main() {

    cin>>l;

    p.push_front(make_pair(1,1));

    suanfa();

    return 0;

}
// Slower C++ solution:
/*

Problem : atcoder 084D

Algorithm : dijkstra

Status :

*/

#include <bits/stdc++.h>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5;



int n,len;

int head[MAXN],dis[MAXN],vis[MAXN];

priority_queue<pii,vector<pii>,greater<pii> > q;



struct Edge{

	int to,next,w;

} e[MAXN * 2];



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

	e[++len].to = v;

	e[len].next = head[u];

	e[len].w = w;

	head[u] = len;

}



int main(){

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

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

    memset(head,-1,sizeof(head));

	scanf("%d",&n);

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

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

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

		dis[i] = INF;

	}

	dis[1] = 1;

	q.push(make_pair(0,1));

	while(!q.empty()){

		int u = q.top().second;

		q.pop();

		if(vis[u])

		    continue;

		vis[u] = true;

		for(int i = head[u];i != -1;i = e[i].next){

			int v = e[i].to;

			if(dis[v] > dis[u] + e[i].w){

				dis[v] = dis[u] + e[i].w;

				q.push(make_pair(dis[v],v));

			}

		}

	}

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

	return 0;

}




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

using namespace std;

deque<pair<int,int> > p;

bool flag[100000001];

int l;

void suanfa(){

    while(p.size()) {

        pair<int,int> 

		now=p.front(); 

		p.pop_front();

        if(flag[now.first]) 

		    continue;

        flag[now.first]=true;

        if(!now.first){

            cout<<now.second<<endl;

            return;

        }

        p.push_front(make_pair(now.first*10%l,now.second));

        p.push_back(make_pair((now.first+1)%l,now.second+1));

    }

}

int main() {

    cin>>l;

    p.push_front(make_pair(1,1));

    suanfa();

    return 0;

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

using namespace std;

const int N=1e5+7;

const int INF=0x3f;

int m,n,k,p,cnt;

int dis[N],head[N];

struct edge

{

    int nx,to,dist;

} e[N*40];

void add_edge(int a,int b,int dist)

{

    cnt++;e[cnt].nx=head[a];e[cnt].to=b;e[cnt].dist=dist;head[a]=cnt;

}

struct node

{

    int pos,dist;

    bool operator<(const node &x) const

    {

        return x.dist<dist;

    }

};

priority_queue<node> que;

bool vis[N];

void dijkstra(int pos)

{

    for (int i=1;i<=N;i++) dis[i]=INF;

    que.push((node){pos,0});dis[pos]=0;

    while (!que.empty())

    {

        node tmp=que.top();que.pop();

        int x=tmp.pos;

        if (vis[x]) continue;

        vis[x]=true;

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

        {

            int y=e[i].to;

            if (dis[y]>dis[x]+e[i].dist)

            {

                dis[y]=dis[x]+e[i].dist;

                if  (!vis[y]) que.push((node) {y,dis[y]});

            }

        }

    }

}

int main()

{

	scanf("%d",&n);

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

	{

		for (int j=0;j<=9;j++)

		add_edge(i,((i-1)*10+j)%n+1,j);

	}

	for (int j=1;j<=9;j++) add_edge(0,j+1,j);

	dijkstra(0);

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

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.7341452247081643x):
#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define il inline 

#define re register

#define LL long long

using namespace std;

const int maxn = 1e6 + 50;

const int mod = 998244353;

const int INF = (1 << 30);

LL read() {

    LL res = 0, f = 1; char ch = ' ';

    while (!isdigit(ch)) { ch = getchar(); if (ch == '-') f = -1; } 

    while (isdigit(ch)) res = (res << 3) + (res << 1) + ch - '0', ch = getchar();

    return res * f;

}



int n, k;

struct node { int x, dis; };

deque<node> q;

int flag[maxn];

void BFS() {

	while (!q.empty()) q.pop_front();

	q.push_front({1, 1});

	while (!q.empty()) {

		node x = q.front(); q.pop_front();

		if (flag[x.x]) continue;

		flag[x.x] = 1;

		if (!x.x) {

			printf("%d\n", x.dis);

			return;

		}

		q.push_front({x.x * 10 % k, x.dis});

		q.push_back({(x.x + 1) % k, x.dis + 1});

	}

}		

int main() {

	k = read();

	BFS();

	return 0;

}
// Slower C++ solution:
/*

Problem : atcoder 084D

Algorithm : dijkstra

Status :

*/

#include <bits/stdc++.h>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5;



int n,len;

int head[MAXN],dis[MAXN],vis[MAXN];

priority_queue<pii,vector<pii>,greater<pii> > q;



struct Edge{

	int to,next,w;

} e[MAXN * 2];



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

	e[++len].to = v;

	e[len].next = head[u];

	e[len].w = w;

	head[u] = len;

}



int main(){

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

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

    memset(head,-1,sizeof(head));

	scanf("%d",&n);

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

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

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

		dis[i] = INF;

	}

	dis[1] = 1;

	q.push(make_pair(0,1));

	while(!q.empty()){

		int u = q.top().second;

		q.pop();

		if(vis[u])

		    continue;

		vis[u] = true;

		for(int i = head[u];i != -1;i = e[i].next){

			int v = e[i].to;

			if(dis[v] > dis[u] + e[i].w){

				dis[v] = dis[u] + e[i].w;

				q.push(make_pair(dis[v],v));

			}

		}

	}

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

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.9970098100567306x):
#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define il inline 

#define re register

#define LL long long

using namespace std;

const int maxn = 1e6 + 50;

const int mod = 998244353;

const int INF = (1 << 30);

LL read() {

    LL res = 0, f = 1; char ch = ' ';

    while (!isdigit(ch)) { ch = getchar(); if (ch == '-') f = -1; } 

    while (isdigit(ch)) res = (res << 3) + (res << 1) + ch - '0', ch = getchar();

    return res * f;

}



int n, k;

struct node { int x, dis; };

deque<node> q;

int flag[maxn];

void BFS() {

	while (!q.empty()) q.pop_front();

	q.push_front({1, 1});

	while (!q.empty()) {

		node x = q.front(); q.pop_front();

		if (flag[x.x]) continue;

		flag[x.x] = 1;

		if (!x.x) {

			printf("%d\n", x.dis);

			return;

		}

		q.push_front({x.x * 10 % k, x.dis});

		q.push_back({(x.x + 1) % k, x.dis + 1});

	}

}		

int main() {

	k = read();

	BFS();

	return 0;

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

#define il inline

#define rg register

using namespace std;

typedef long long LL;

const LL m_63=1061109567;

const LL m_127=2139062143;

const int inf=2147483647;

const double pi=atan(1.0)*4.0;

const LL llf=9223372036854775807;

const LL N=1e6+7;

const int M=1e6;

int n,d[N],flag[N];

int num,b[N],w[N],p[N],nt[N];

il LL read(){

    LL x(0),ff(1);char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')ff=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*ff;

}

il void fre(){

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

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

}

il void spfa(){

	queue<int>q;

	memset(d,127,sizeof(d));

	memset(flag,0,sizeof(flag));

	q.push(1);d[1]=0;

	while(!q.empty()){

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

		int e=p[k];flag[k]=0;

		while(e){

			int kk=b[e];

			if(d[kk]>d[k]+w[e]){

				d[kk]=d[k]+w[e];

				if(!flag[kk]){

					flag[kk]=1;

					q.push(kk);

				}

			}

			e=nt[e];

		}

	}

}

il void add(int x,int y,int z){b[++num]=y,w[num]=z,nt[num]=p[x],p[x]=num;}

int main(){

//	fre();

//	cout<<sum(112)<<endl;return 0;

//https://www.luogu.org/problemnew/solution/AT3621

//https://blog.csdn.net/winter2121/article/details/81393967

//Ã¿Ò»¸öÊý¶¼¿ÉÒÔÓÉ1Í¨¹ýÒÔÏÂÁ½ÖÖÊµÏÖ

//*10 Î»ÊýºÍ²»±ä

//+1 Î»ÊýºÍ+1

//	n=read();

//	for(rg int i=1;i<=n;++i){

		int k=read();

		for(rg int j=0;j<k;++j){

			add(j,(j+1)%k,1);

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

//			cout<<i<<' '<<(i+1)%k<<" 1"<<endl;

//			cout<<i<<' '<<(i*10)%k<<" 0"<<endl;

		}

		spfa();

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

//		memset(p,0,sizeof(p));num=0;

//	}

	return 0;

}

/*

5 6 10

1 2 4

1 4 1

4 3 1

2 5 1

4 5 2

3 2 1

1

3

1

2 2



*/

// Faster C++ solution for the same problem (measured speedup: 9.26275826425649x):
#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define il inline 

#define re register

#define LL long long

using namespace std;

const int maxn = 1e6 + 50;

const int mod = 998244353;

const int INF = (1 << 30);

LL read() {

    LL res = 0, f = 1; char ch = ' ';

    while (!isdigit(ch)) { ch = getchar(); if (ch == '-') f = -1; } 

    while (isdigit(ch)) res = (res << 3) + (res << 1) + ch - '0', ch = getchar();

    return res * f;

}



int n, k;

struct node { int x, dis; };

deque<node> q;

int flag[maxn];

void BFS() {

	while (!q.empty()) q.pop_front();

	q.push_front({1, 1});

	while (!q.empty()) {

		node x = q.front(); q.pop_front();

		if (flag[x.x]) continue;

		flag[x.x] = 1;

		if (!x.x) {

			printf("%d\n", x.dis);

			return;

		}

		q.push_front({x.x * 10 % k, x.dis});

		q.push_back({(x.x + 1) % k, x.dis + 1});

	}

}		

int main() {

	k = read();

	BFS();

	return 0;

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

#define il inline

#define rg register

using namespace std;

typedef long long LL;

const LL m_63=1061109567;

const LL m_127=2139062143;

const int inf=2147483647;

const double pi=atan(1.0)*4.0;

const LL llf=9223372036854775807;

const LL N=1e6+7;

const int M=1e6;

int n,d[N],flag[N];

int num,b[N],w[N],p[N],nt[N];

il LL read(){

    LL x(0),ff(1);char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')ff=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*ff;

}

il void fre(){

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

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

}

il void spfa(){

	queue<int>q;

	memset(d,127,sizeof(d));

	memset(flag,0,sizeof(flag));

	q.push(1);d[1]=0;

	while(!q.empty()){

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

		int e=p[k];flag[k]=0;

		while(e){

			int kk=b[e];

			if(d[kk]>d[k]+w[e]){

				d[kk]=d[k]+w[e];

				if(!flag[kk]){

					flag[kk]=1;

					q.push(kk);

				}

			}

			e=nt[e];

		}

	}

}

il void add(int x,int y,int z){b[++num]=y,w[num]=z,nt[num]=p[x],p[x]=num;}

int main(){

//	fre();

//	cout<<sum(112)<<endl;return 0;

//https://www.luogu.org/problemnew/solution/AT3621

//https://blog.csdn.net/winter2121/article/details/81393967

//Ã¿Ò»¸öÊý¶¼¿ÉÒÔÓÉ1Í¨¹ýÒÔÏÂÁ½ÖÖÊµÏÖ

//*10 Î»ÊýºÍ²»±ä

//+1 Î»ÊýºÍ+1

//	n=read();

//	for(rg int i=1;i<=n;++i){

		int k=read();

		for(rg int j=0;j<k;++j){

			add(j,(j+1)%k,1);

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

//			cout<<i<<' '<<(i+1)%k<<" 1"<<endl;

//			cout<<i<<' '<<(i*10)%k<<" 0"<<endl;

		}

		spfa();

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

//		memset(p,0,sizeof(p));num=0;

//	}

	return 0;

}

/*

5 6 10

1 2 4

1 4 1

4 3 1

2 5 1

4 5 2

3 2 1

1

3

1

2 2



*/

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

#define LL long long 

using namespace std;



inline int read(){

	int res=0,f=1;char ch=' ';

	while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}

	while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}

	return res*f;

}

const int N=1e5+5;

const int mod=998244353;

int n,S,T;

int d[N],flag[N];

int head[N*20],to[N*20],w[N*20],nxt[N*20],cnt;

inline void qxx(int x,int y,int z){

	cnt++;nxt[cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;

}

inline void SPFA(){

	memset(d,63,sizeof(d));

	queue<int>q;q.push(S);d[S]=0;flag[S]=1;

	while(!q.empty()){

		int k=q.front();q.pop();flag[k]=0;

		for(register int i=head[k];i;i=nxt[i]){

			int kk=to[i];

			if(d[kk]>d[k]+w[i]){

				d[kk]=d[k]+w[i];

				if(!flag[kk]){

					flag[kk]=1;q.push(kk);

				}

			}

		}

	}

}

int main(){

	n=read();

	S=0;T=1;

	for(register int i=1;i<=n;i++)

		for(register int j=0;j<=9;j++)

			qxx(i,((i-1)*10+j)%n+1,j);

	for(register int i=1;i<=9;i++) qxx(0,i+1,i);

	SPFA();

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

	return 0;

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

#define il inline

#define rg register

using namespace std;

typedef long long LL;

const LL m_63=1061109567;

const LL m_127=2139062143;

const int inf=2147483647;

const double pi=atan(1.0)*4.0;

const LL llf=9223372036854775807;

const LL N=1e6+7;

const int M=1e6;

int n,d[N],flag[N];

int num,b[N],w[N],p[N],nt[N];

il LL read(){

    LL x(0),ff(1);char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')ff=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*ff;

}

il void fre(){

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

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

}

il void spfa(){

	queue<int>q;

	memset(d,127,sizeof(d));

	memset(flag,0,sizeof(flag));

	q.push(1);d[1]=0;

	while(!q.empty()){

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

		int e=p[k];flag[k]=0;

		while(e){

			int kk=b[e];

			if(d[kk]>d[k]+w[e]){

				d[kk]=d[k]+w[e];

				if(!flag[kk]){

					flag[kk]=1;

					q.push(kk);

				}

			}

			e=nt[e];

		}

	}

}

il void add(int x,int y,int z){b[++num]=y,w[num]=z,nt[num]=p[x],p[x]=num;}

int main(){

//	fre();

//	cout<<sum(112)<<endl;return 0;

//https://www.luogu.org/problemnew/solution/AT3621

//https://blog.csdn.net/winter2121/article/details/81393967

//Ã¿Ò»¸öÊý¶¼¿ÉÒÔÓÉ1Í¨¹ýÒÔÏÂÁ½ÖÖÊµÏÖ

//*10 Î»ÊýºÍ²»±ä

//+1 Î»ÊýºÍ+1

//	n=read();

//	for(rg int i=1;i<=n;++i){

		int k=read();

		for(rg int j=0;j<k;++j){

			add(j,(j+1)%k,1);

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

//			cout<<i<<' '<<(i+1)%k<<" 1"<<endl;

//			cout<<i<<' '<<(i*10)%k<<" 0"<<endl;

		}

		spfa();

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

//		memset(p,0,sizeof(p));num=0;

//	}

	return 0;

}

/*

5 6 10

1 2 4

1 4 1

4 3 1

2 5 1

4 5 2

3 2 1

1

3

1

2 2



*/

// Faster C++ solution for the same problem (measured speedup: 6.441874337129054x):
#include<iostream>

#include<cstring>

#include<queue>

using namespace std;

namespace fio {

	streambuf* in = cin.rdbuf();

	char bb[1000000], * s = bb, * t = bb;

#define gc() (s==t&&(t=(s=bb)+in->sgetn(bb,1000000),s==t)?EOF:*s++)

	inline int read() {

		int x = 0;

		char ch = gc();

		while (ch < 48)ch = gc();

		while (ch >= 48)x = x * 10 + ch - 48, ch = gc();

		return x;

	}

}using fio::read;

int sst[100005];

int k;

queue<int>ygy;

int main() {

	cin >> k;

	ygy.push(1), memset(sst, 0x3f, sizeof(sst)), sst[1] = 1;

	while (ygy.size()) {

		int thx = ygy.front(); ygy.pop();

		if (sst[thx] > sst[0])continue;

		if (sst[(thx + 1) % k] > sst[thx] + 1)sst[(thx + 1) % k] = sst[thx] + 1, ygy.push((thx + 1) % k);

		if (sst[thx * 10 % k] > sst[thx])sst[thx * 10 % k] = sst[thx], ygy.push(thx * 10 % k);

	}

	cout << sst[0];

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

#define il inline

#define rg register

using namespace std;

typedef long long LL;

const LL m_63=1061109567;

const LL m_127=2139062143;

const int inf=2147483647;

const double pi=atan(1.0)*4.0;

const LL llf=9223372036854775807;

const LL N=1e6+7;

const int M=1e6;

int n,d[N],flag[N];

int num,b[N],w[N],p[N],nt[N];

il LL read(){

    LL x(0),ff(1);char ch=getchar();

    while(ch<'0'||ch>'9'){

        if(ch=='-')ff=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*ff;

}

il void fre(){

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

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

}

il void spfa(){

	queue<int>q;

	memset(d,127,sizeof(d));

	memset(flag,0,sizeof(flag));

	q.push(1);d[1]=0;

	while(!q.empty()){

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

		int e=p[k];flag[k]=0;

		while(e){

			int kk=b[e];

			if(d[kk]>d[k]+w[e]){

				d[kk]=d[k]+w[e];

				if(!flag[kk]){

					flag[kk]=1;

					q.push(kk);

				}

			}

			e=nt[e];

		}

	}

}

il void add(int x,int y,int z){b[++num]=y,w[num]=z,nt[num]=p[x],p[x]=num;}

int main(){

//	fre();

//	cout<<sum(112)<<endl;return 0;

//https://www.luogu.org/problemnew/solution/AT3621

//https://blog.csdn.net/winter2121/article/details/81393967

//Ã¿Ò»¸öÊý¶¼¿ÉÒÔÓÉ1Í¨¹ýÒÔÏÂÁ½ÖÖÊµÏÖ

//*10 Î»ÊýºÍ²»±ä

//+1 Î»ÊýºÍ+1

//	n=read();

//	for(rg int i=1;i<=n;++i){

		int k=read();

		for(rg int j=0;j<k;++j){

			add(j,(j+1)%k,1);

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

//			cout<<i<<' '<<(i+1)%k<<" 1"<<endl;

//			cout<<i<<' '<<(i*10)%k<<" 0"<<endl;

		}

		spfa();

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

//		memset(p,0,sizeof(p));num=0;

//	}

	return 0;

}

/*

5 6 10

1 2 4

1 4 1

4 3 1

2 5 1

4 5 2

3 2 1

1

3

1

2 2



*/

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

#define INF 1000000000

#define LINF 1000000000000000000

#define MOD 1000000007

#define INF63 1061109567

#define INF127 9187201950435737471

#define F first

#define S second

#define ll long long

#define N 100010

using namespace std;

int k;

int dist[N];

deque<int> dq;

int main(){

	int n,x,t;

	cin>>k;

	memset(dist,63,sizeof(dist));

	dq.push_front(1);

	dist[1]=1;

	while(!dq.empty())

	{

		x=dq.front();

		dq.pop_front();

		t=(x*10)%k;

		if(dist[t]>dist[x])

		{

			dist[t]=dist[x];

			dq.push_front(t);

		}

		t=(x+1)%k;

		if(dist[t]>dist[x]+1)

		{

			dist[t]=dist[x]+1;

			dq.push_back(t);

		}

	}

	cout<<dist[0]<<endl;

	return 0;

}