stablegradients/pie-gem5-pairs huggingface dataset:
// 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.254464929920091x):
#include <bits/stdc++.h>



using namespace std;



#define ll long long

#define ull unsigned long long

#define re register

#define il inline

#define inf 0x3f3f3f

using namespace std;



const int MAXN = 1e5 + 10;

int n, m, first[MAXN], tot, d[MAXN], s, t;



struct edge {

  int from, v, w;

} e[20 * MAXN];

struct Node {

  int x, d;

  bool operator<(const Node &b) const { return d > b.d; }

} cyc;

priority_queue<Node> q;

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

  tot++;

  e[tot].v = v;

  e[tot].w = w;

  e[tot].from = first[u];

  first[u] = tot;

}

int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  cin >> n;

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

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

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

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

    insert(0, j + 1, j);

  s = 0;

  t = 1;

  memset(d, 0x3f, sizeof d);

  d[s] = 0;

  q.push((Node){s, d[s]});

  while (!q.empty()) {

    cyc = q.top();

    q.pop();

    if (cyc.d != d[cyc.x])

      continue;

    register int x = cyc.x;

    for (register int i = first[x]; i; i = e[i].from)

      if (d[e[i].v] > d[x] + e[i].w) {

        d[e[i].v] = d[x] + e[i].w;

        q.push((Node){e[i].v, d[e[i].v]});

      }

  }

  return cout << d[t], 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.581370636486224x):
#include <bits/stdc++.h>

using namespace std;



deque<int> q;

int dis[100005];



int main() {

	int n;

	scanf("%d",&n);

	memset(dis,0x7f,sizeof(dis));

	dis[1]=1;

	q.push_back(1);

	while(!q.empty()) {

		int u=q.front();

		q.pop_front();

		if(dis[(u*10)%n]>dis[u]) {

			dis[(u*10)%n]=dis[u];

			q.push_front((u*10)%n);

		}

		if(dis[(u+1)%n]>dis[u]+1) {

			dis[(u+1)%n]=dis[u]+1;

			q.push_back((u+1)%n);

		}

	}

	printf("%d\n",dis[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.022472935623819x):
#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define Maxn 100005

typedef long long ll;

int n,tot;

int hea[Maxn],ds[Maxn];

int ver[Maxn*2],nex[Maxn*2],edg[Maxn*2];

void add(int u,int v,int d)

{

	 ver[++tot]=v,edg[tot]=d,nex[tot]=hea[u],hea[u]=tot;

}

struct ren

{

	 int num;

	 int Cost;

	 friend bool operator < (ren x,ren y)

	 {

	 	 return x.Cost>y.Cost;

	 }

}cur,vis;

priority_queue<ren> q;

int dj()

{

	 memset(ds,inf,sizeof(ds));

	 cur.num=1,cur.Cost=0;

	 q.push(cur);

	 ds[1]=0;

	 while(!q.empty())

	 {

	 	 cur=q.top();

	 	 q.pop();

	 	 for(int i=hea[cur.num];i;i=nex[i])

	 	 {

	 	 	 if(ds[cur.num]+edg[i]<ds[ver[i]])

	 	 	 {

	 	 	 	 ds[ver[i]]=ds[cur.num]+edg[i];

	 	 	 	 vis.num=ver[i],vis.Cost=ds[ver[i]];

	 	 	 	 q.push(vis);

			 }

		 }

	 }

	 return ds[0]+1;

}

int main()

{

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

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

	 scanf("%d",&n);

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

	 {

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

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

	 }

	 printf("%d\n",dj());

     //fclose(stdin);

     //fclose(stdout);

     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.7227288839686439x):
#include <bits/stdc++.h>



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	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.993232625036569x):
#include <bits/stdc++.h>



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	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.207134322469207x):
#include <bits/stdc++.h>



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

}
// Slower C++ solution:
#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;

}

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



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

}
// Slower C++ solution:
#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];

}

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



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

}
// Slower C++ solution:
#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;

}

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



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

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



using namespace std;



#define ll long long

#define ull unsigned long long

#define re register

#define il inline

#define inf 0x3f3f3f

using namespace std;



const int MAXN = 1e5 + 10;

int n, m, first[MAXN], tot, d[MAXN], s, t;



struct edge {

  int from, v, w;

} e[20 * MAXN];

struct Node {

  int x, d;

  bool operator<(const Node &b) const { return d > b.d; }

} cyc;

priority_queue<Node> q;

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

  tot++;

  e[tot].v = v;

  e[tot].w = w;

  e[tot].from = first[u];

  first[u] = tot;

}

int main() {

  ios::sync_with_stdio(false);

  cin.tie(0);

  cin >> n;

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

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

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

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

    insert(0, j + 1, j);

  s = 0;

  t = 1;

  memset(d, 0x3f, sizeof d);

  d[s] = 0;

  q.push((Node){s, d[s]});

  while (!q.empty()) {

    cyc = q.top();

    q.pop();

    if (cyc.d != d[cyc.x])

      continue;

    register int x = cyc.x;

    for (register int i = first[x]; i; i = e[i].from)

      if (d[e[i].v] > d[x] + e[i].w) {

        d[e[i].v] = d[x] + e[i].w;

        q.push((Node){e[i].v, d[e[i].v]});

      }

  }

  return cout << d[t], 0;

}


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



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

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

using namespace std;



deque<int> q;

int dis[100005];



int main() {

	int n;

	scanf("%d",&n);

	memset(dis,0x7f,sizeof(dis));

	dis[1]=1;

	q.push_back(1);

	while(!q.empty()) {

		int u=q.front();

		q.pop_front();

		if(dis[(u*10)%n]>dis[u]) {

			dis[(u*10)%n]=dis[u];

			q.push_front((u*10)%n);

		}

		if(dis[(u+1)%n]>dis[u]+1) {

			dis[(u+1)%n]=dis[u]+1;

			q.push_back((u+1)%n);

		}

	}

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

}

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



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

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

using namespace std;

#define inf 0x3f3f3f3f

#define Maxn 100005

typedef long long ll;

int n,tot;

int hea[Maxn],ds[Maxn];

int ver[Maxn*2],nex[Maxn*2],edg[Maxn*2];

void add(int u,int v,int d)

{

	 ver[++tot]=v,edg[tot]=d,nex[tot]=hea[u],hea[u]=tot;

}

struct ren

{

	 int num;

	 int Cost;

	 friend bool operator < (ren x,ren y)

	 {

	 	 return x.Cost>y.Cost;

	 }

}cur,vis;

priority_queue<ren> q;

int dj()

{

	 memset(ds,inf,sizeof(ds));

	 cur.num=1,cur.Cost=0;

	 q.push(cur);

	 ds[1]=0;

	 while(!q.empty())

	 {

	 	 cur=q.top();

	 	 q.pop();

	 	 for(int i=hea[cur.num];i;i=nex[i])

	 	 {

	 	 	 if(ds[cur.num]+edg[i]<ds[ver[i]])

	 	 	 {

	 	 	 	 ds[ver[i]]=ds[cur.num]+edg[i];

	 	 	 	 vis.num=ver[i],vis.Cost=ds[ver[i]];

	 	 	 	 q.push(vis);

			 }

		 }

	 }

	 return ds[0]+1;

}

int main()

{

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

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

	 scanf("%d",&n);

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

	 {

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

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

	 }

	 printf("%d\n",dj());

     //fclose(stdin);

     //fclose(stdout);

     return 0;

}

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



using namespace std;



#define M 1000005



int k;

int vis[M];



deque< pair<int, int> > dq;

#define mp(x, y) make_pair(x, y)

#define pi pair<int, int>



void bfs()

{

	dq.push_back(mp(1, 1));

	while (!dq.empty())

	{

		pi x = dq.front(); dq.pop_front();

		if (vis[x.first]) continue; vis[x.first] = 1;

		if (!x.first) { cout << x.second; return; }

		dq.push_front(mp((x.first*10) % k, x.second));

		dq.push_back(mp((x.first+1) % k, x.second + 1));

	}

}



int main()

{

	cin >> k;

	bfs();

	return 0;

}