stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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]);

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")

typedef long long lint;

typedef unsigned int uint;

typedef pair<int, int> pii;

typedef pair<lint, lint> pll;

typedef unsigned long long ulint;

#define endl '\n'

#define fst first

#define sed second

#define pb push_back

#define mp make_pair

#define rint register int

#define newline putchar('\n')

#define leave_space putchar(' ')

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

#define reveal(x) cerr << #x << " = " << (x) << endl

#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)

#define per(it, f, e) for (rint it = (f); it >= (e); --it)

const int MAXN = 1e5 + 5;

queue<pii> que;

int dis[MAXN];

int main() {

	ios::sync_with_stdio(false);

	cin.tie(NULL), cout.tie(NULL);

	int k;

	cin >> k;

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

	rep (i, 1, 9) {

		que.push(mp(i % k, i));

		dis[i % k] = min(i, dis[i % k]);

	}

	while (!que.empty()) {

		pii u = que.front(); que.pop();

		if (!u.fst) continue;

		if (u.sed != dis[u.fst]) continue;

		rep (i, 0, 9) {

			int vi = (u.fst * 10 + i) % k;

			int vj = u.sed + i;

			if (dis[vi] > vj) {

				dis[vi] = vj;

				que.push(pii(vi, vj));

			}

		}

	}

	cout << dis[0] << endl;

	return 0;

}

// Optimized solution to the same problem (faster):
//https://www.luogu.org/problem/AT3621

#include<bits/stdc++.h>

#define ll long long

#define inf 1000000000

#define mp make_pair

#define pii pair<int,int>

#define pb push_back

#define ri register int

#define rep(i,a,b) for(ri i=(a);i<=(b);++i)

#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))

#define REP(i,a,b) for(ri i=(a);i>=(b);--i)

#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))

#define fi first

#define se second

using namespace std;



inline int read(){

	ri x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();

	return x*f;

}

inline void write(ri x){

	if(x<0) putchar('-'),x=-x;

	if(x>9) write(x/10);

	putchar(x%10+'0');

}



const int N=1e6+5;

int n;

bool vis[N];

deque<pii> q;

int main()

{

	n=read();q.push_front(mp(1,1));

	while(1){

		pii t=q.front();q.pop_front();

		if(vis[t.fi]) continue;

		vis[t.fi]=1;

		if(!t.fi) return write(t.se),0;

		q.push_front(mp(t.fi*10%n,t.se));

		q.push_back(mp((t.fi+1)%n,t.se+1));

	}

	return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define maxk 100010

using namespace std;



struct Node{

	int dis,pos;

	bool operator <(const Node &x)const{

		return x.dis<dis;

	}

};



struct Node_e{

	int v,w,next;

};



Node_e edge[maxk*4];

int dist[maxk],vis[maxk],head[maxk*4];

int num=0;

int k;



void addedge(int x,int y,int z)

{

	edge[++num].v=y;

	edge[num].w=z;

	edge[num].next=head[x];

	head[x]=num;

}



priority_queue<Node> q;



void dijkstra()

{

	memset(vis,0,sizeof(vis));

	memset(dist,0x3f3f3f3f,sizeof(dist));

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

	dist[1]=1;

	q.push((Node){0,1});

	while(!q.empty()){

		Node tmp=q.top();q.pop();

		int u=tmp.pos;

		if(vis[u])continue;

		for(int i=head[u];i;i=edge[i].next){

			int v=edge[i].v;

			if(dist[v]>dist[u]+edge[i].w){

				dist[v]=dist[u]+edge[i].w;

				if(!vis[v]){

					q.push((Node){dist[v],v});

				}

			}

		}

	}

}



int main()

{

	scanf("%d",&k);

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

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

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

	}

	dijkstra();

	printf("%d",dist[0]);

	return 0;

}

// Optimized solution to the same problem (faster):
//https://www.luogu.org/problem/AT3621

#include<bits/stdc++.h>

#define ll long long

#define inf 1000000000

#define mp make_pair

#define pii pair<int,int>

#define pb push_back

#define ri register int

#define rep(i,a,b) for(ri i=(a);i<=(b);++i)

#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))

#define REP(i,a,b) for(ri i=(a);i>=(b);--i)

#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))

#define fi first

#define se second

using namespace std;



inline int read(){

	ri x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();

	return x*f;

}

inline void write(ri x){

	if(x<0) putchar('-'),x=-x;

	if(x>9) write(x/10);

	putchar(x%10+'0');

}



const int N=1e6+5;

int n;

bool vis[N];

deque<pii> q;

int main()

{

	n=read();q.push_front(mp(1,1));

	while(1){

		pii t=q.front();q.pop_front();

		if(vis[t.fi]) continue;

		vis[t.fi]=1;

		if(!t.fi) return write(t.se),0;

		q.push_front(mp(t.fi*10%n,t.se));

		q.push_back(mp((t.fi+1)%n,t.se+1));

	}

	return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <algorithm>

#include <cstdio>

#include <cstring>

#include <queue>



const int N = 2e5 + 52;

struct edge {

	int to, next, w;

} e[N << 1];

int n, head[N], cnt;

void ad(int x, int y, int z) { e[++cnt] = {y, x[head], z}, x[head] = cnt; }



std::queue<int> q;

int dis[N];

int main() {

	memset(head, -1, sizeof head);

	memset(dis, 0x3f, sizeof dis), dis[1] = 1;

	scanf("%d", &n);

	for (int i = 1; i < n; i++) ad(i, (i + 1) % n, 1);

	for (int i = 1; i < n; i++) ad(i, i * 10 % n, 0);

	for (q.push(1); !q.empty(); q.pop())

		for (int x = q.front(), i = x[head], nx; ~i; i = e[i].next)

			if ((nx = e[i].to)[dis] > x[dis] + e[i].w) nx[dis] = x[dis] + e[i].w, q.push(nx);

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

}

// Optimized solution to the same problem (faster):
//https://www.luogu.org/problem/AT3621

#include<bits/stdc++.h>

#define ll long long

#define inf 1000000000

#define mp make_pair

#define pii pair<int,int>

#define pb push_back

#define ri register int

#define rep(i,a,b) for(ri i=(a);i<=(b);++i)

#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))

#define REP(i,a,b) for(ri i=(a);i>=(b);--i)

#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))

#define fi first

#define se second

using namespace std;



inline int read(){

	ri x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();

	return x*f;

}

inline void write(ri x){

	if(x<0) putchar('-'),x=-x;

	if(x>9) write(x/10);

	putchar(x%10+'0');

}



const int N=1e6+5;

int n;

bool vis[N];

deque<pii> q;

int main()

{

	n=read();q.push_front(mp(1,1));

	while(1){

		pii t=q.front();q.pop_front();

		if(vis[t.fi]) continue;

		vis[t.fi]=1;

		if(!t.fi) return write(t.se),0;

		q.push_front(mp(t.fi*10%n,t.se));

		q.push_back(mp((t.fi+1)%n,t.se+1));

	}

	return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



const int maxn=100005;

int n,m,dis[maxn]={0};

int s,t;

struct edge{

	int to;

	int weight;

};

vector<edge> GV[maxn];

struct qnode{

	int u,len;

	bool operator <(const qnode &tmp) const{

		return len>tmp.len;

	}

};

priority_queue<qnode> pq;



int main(){

	scanf("%d",&n);  

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

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

			edge tmp;

			tmp.to=((i-1)*10+j)%n+1,tmp.weight=j;

			GV[i].push_back(tmp);

		}

	for(int i=1;i<=9;i++){

		edge tmp;

		tmp.to=i+1,tmp.weight=i;

		GV[0].push_back(tmp);

	}

	

	s=0,t=1;

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

	dis[0]=0;

	pq.push((qnode){0,dis[0]});

	

	while(!pq.empty()){

		qnode nowp=pq.top();

		pq.pop();

		if(nowp.len!=dis[nowp.u])  continue;

		for(int i=0;i<GV[nowp.u].size();i++){

			if (dis[GV[nowp.u][i].to]>dis[nowp.u]+GV[nowp.u][i].weight){

                dis[GV[nowp.u][i].to]=dis[nowp.u]+GV[nowp.u][i].weight;

				pq.push((qnode){GV[nowp.u][i].to,dis[GV[nowp.u][i].to]});

            }

		}

	}

	

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

	

	return 0;

}

// Optimized solution to the same problem (faster):
//https://www.luogu.org/problem/AT3621

#include<bits/stdc++.h>

#define ll long long

#define inf 1000000000

#define mp make_pair

#define pii pair<int,int>

#define pb push_back

#define ri register int

#define rep(i,a,b) for(ri i=(a);i<=(b);++i)

#define rep2(i,a,b,c) for(ri i=(a);i<=(b);i+=(c))

#define REP(i,a,b) for(ri i=(a);i>=(b);--i)

#define REP2(i,a,b,c) for(ri i=(a);i>=(b);i-=(c))

#define fi first

#define se second

using namespace std;



inline int read(){

	ri x=0,f=1;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();

	return x*f;

}

inline void write(ri x){

	if(x<0) putchar('-'),x=-x;

	if(x>9) write(x/10);

	putchar(x%10+'0');

}



const int N=1e6+5;

int n;

bool vis[N];

deque<pii> q;

int main()

{

	n=read();q.push_front(mp(1,1));

	while(1){

		pii t=q.front();q.pop_front();

		if(vis[t.fi]) continue;

		vis[t.fi]=1;

		if(!t.fi) return write(t.se),0;

		q.push_front(mp(t.fi*10%n,t.se));

		q.push_back(mp((t.fi+1)%n,t.se+1));

	}

	return 0; 

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define ll long long

#define in(a) a=read()

#define out(a) printf("%d\n",a)

inline ll read(){

    char c=getchar();ll f=1,x=0;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

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

    return x*f;

}

#define mod 1000000007

void MOD(int &x){if(x>=mod)x-=mod;}

#define maxn 100010

#define inf (1<<30)



int l,head[maxn],to[maxn*2],nxt[maxn*2],v[maxn*2];

void add(int x,int y,int z){

	nxt[++l]=head[x];head[x]=l;to[l]=y;v[l]=z;

}

int bfs[maxn*10],d[maxn],u[maxn];

int main(){

	int n;

	in(n);

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

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

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

	}

	memset(d,0x3f,sizeof(d));

	int l=1,r=2;

	bfs[l]=0;d[0]=0;

	while(l<r){

		int x=bfs[l++];u[x]=0;

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

			int c=to[i];

			if(d[x]+v[i]<d[c]){

				d[c]=d[x]+v[i];

				if(!u[c]){

					u[c]=1;

					bfs[r++]=c;

				}

			}

		}

	}

	int ans=inf;

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

		if((i+1)%n==0)ans=min(ans,d[i]+1);

		if(i*10%n==0)ans=min(ans,d[i]);

	}

	out(ans);

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <string>

#include <queue>

#include <deque>

#define N 101000

template<typename T> inline void read(T &x) {

	x = 0; char c = getchar(); bool flag = false;

	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }

	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }

	if (flag)	x = -x;

}

using namespace std;

int n;

int dis[N];

deque<int> q, qq;

inline void bfs() {

	//dis[1] = 1;

	q.push_back(1);

	qq.push_back(1);

	while (q.size()) {

		int p = q.front();

		q.pop_front();

		int v = qq.front();

		qq.pop_front();

		if (dis[p])	continue;

		dis[p] = v;

		if (!p)	return ;

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

		qq.push_back(dis[p] + 1);

		q.push_front(p * 10 % n);

		qq.push_front(dis[p]);

		//printf("p = %d, dis = %d\n", p, dis[p]);

		//printf("p = %d\n", p);

		/*

		if (!p)	return ;

		if (!dis[(p + 1) % n])	dis[(p + 1) % n] = dis[p] + 1, q.push_back((p + 1) % n);

		//else	printf("p + 1 mod n = %d, dis = %d\n", (p + 1) % n, dis[(p + 1) % n]);

		if (!dis[p * 10 % n])	dis[p * 10 % n] = dis[p], q.push_front(p * 10 % n);

		//else	printf("p * 10 mod n = %d, dis = %d\n", p * 10 % n, dis[p * 10 % n]);

		*/

	}

}



int main() {

	read(n);

	bfs();

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

	return 0;

}

/*

6 3

41 5

79992 36

7 2(1001)

*/

// Fastest known solution for this problem:
// Original C++ solution (slower):
#define FOR(i,j,n) for (int i=(j);i<(n);i++)

#define REP(i,n) for (int i=0;i<(n);i++)

#define I(n) scanf("%d", &(n))

#define pb(n) push_back((n))

#define mp(i,j) make_pair((i),(j))

#include <bits/stdc++.h>

using namespace std;



long long d[100001];

int k,m;



void check(int a, int ans, int mod){

    if (ans > 45 || d[a] & ((long long)1 << ans)){

        return;

    }

    d[a] |= (long long)1 << ans;

    if (a == 0 && 0 < ans && ans < m){ m = ans; }

    REP(i,10) check((a*10+i)%mod,ans+i,mod);

}



int main(){

    I(k);

    m = 10000;

    check(0,0,k);

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

}


// Optimized solution to the same problem (faster):
#include <stdio.h>

typedef long long ll;ll d[1<<17];int k,m;void f(int a,int n,int o){if(n>45||d[a]&(ll)1<<n)return;d[a]|=(ll)1<<n;if(!a&&n&&n<m)m=n;for(int i=0;i<10;i++)f((a*10+i)%o,n+i,o);}int main(){scanf("%d",&k);m=45;f(0,0,k);printf("%d\n",m);}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <iomanip>

#include <string>

#include <sstream>

#include <fstream>

#include <cassert>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <numeric>

#include <utility>

#include <vector>

#include <queue>

#include <map>

#include <set>

#include <unordered_map>

#include <unordered_set>

#include <bitset>

#include <complex>

using namespace std;

using ll = long long;

using ld = long double;

using pii = pair<int, int>;

constexpr int MAXN = 100005;

int k;

int dist[MAXN][10];

int main() {

	ios_base::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	scanf("%d", &k);

	deque<pii> q;

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

	dist[1][1] = 1;

	q.push_back({1, 1});

	while (!q.empty()) {

		pii x = q.front();

		q.pop_front();

		int by_ten = (x.first * 10) % k;

		if (dist[by_ten][0] == -1) {

			dist[by_ten][0] = dist[x.first][x.second];

			q.push_front({by_ten, 0});

		}

		int add_one = (x.first + 1) % k;

		if (x.second + 1 < 10 and dist[add_one][x.second + 1] == -1) {

			dist[add_one][x.second + 1] = dist[x.first][x.second] + 1;

			q.push_back({add_one, x.second + 1});

		}

	}

	int res = 987654321;

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

		if (dist[0][i] == -1) continue;

		res = min(res, dist[0][i]);

	}

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

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <ostream>

#include <istream>

#include <cmath>

#include <string>

#include <vector>

#include <sstream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <vector>

#include <set>

#define pb push_back

#define ppb pop_back

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

#define for1(i, n) for (int i = 1; i <= int(n); i++)

#define forv(i, v) forn(i, v.size())

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

#define pb push_back

#define mp make_pair

#define CIN_FILE "input.txt"

#define COUT_FILE "output.txt"

#define pi 3.1415926535897932

#define NMAX 100005

#define INF 1000000007

typedef pair<int, int> pii;

typedef long long ll;

typedef long double ld;

int K,dist[100000];

deque<int> todo;

int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin>>K;

	for(int i=0; i<K; i++)dist[i]=INF;

	dist[1]=1;

	todo.pb(1);

	while(todo.size()) {

		int x=todo.front();

		todo.pop_front();

		if(dist[(10*x)%K]>dist[x]) {

			dist[(10*x)%K]=dist[x];

			todo.push_front((10*x)%K) ;

		}

		if(dist[(x+1)%K]>dist[x]+1) {

			dist[(x+1)%K]=dist[x]+1;

			todo.push_back((x+1)%K);

		}

	}

	cout<<dist[0];

	return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



const int MAX_N=1e5+10;

const int INF=1e9+10;



int K,N,M,dist[MAX_N];

vector <pair<int,int> > g[MAX_N];

priority_queue <pair<int,int> > Q;



void get_dijk(){

	for(int i=0;i<MAX_N;i++) dist[i]=INF;

	dist[1]=1;

	Q.push(make_pair(-dist[1],1));

	while(Q.size()){

		int val=-Q.top().first,x=Q.top().second;

		Q.pop();

		if(dist[x]<val) continue;

		for(int i=0;i<g[x].size();i++){

			int cost=g[x][i].first,to=g[x][i].second;

			if(dist[to]>cost+dist[x]){

				dist[to]=cost+dist[x];

				Q.push(make_pair(-dist[to],to));

			}

		}

	}

}



int main(){

	cin>>K;

	for(int i=1;i<K;i++){

		g[i].push_back(make_pair(0,i*10%K));

		g[i].push_back(make_pair(1,(i+1)%K));

	}

	get_dijk();

	cout<<dist[0]<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



#define int long long

#define pii pair<int,int> 



int K;

int dist[100010];

bool inh[100010];



main()

{

	ios::sync_with_stdio(false);

	

	cin>>K;

	

	int ans=1000000010;

	

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

	priority_queue<pii> H;

	dist[1]=1;

	H.push({-1,1});

	inh[1]=true;

	

	while(!H.empty())

	{

		int u=H.top().second; H.pop();

		if(!inh[u]) continue;

		inh[u]=false; // cout<<u<<endl;

		if(u%K==0) ans=min(ans,dist[u]);

		int v=u*10%K;

		if(dist[v]==-1 || dist[v]>dist[u])

		{

			dist[v]=dist[u];

			H.push({-dist[v],v});

			inh[v]=true;

		}

		v=(u+1)%K;

		if(dist[v]==-1 || dist[v]>dist[u]+1)

		{

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

			H.push({-dist[v],v});

			inh[v]=true;

		}

	}

	cout<<ans<<endl;

	

	return 0;

}






















// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <fstream>

#include <cstdio>

#include <cassert>

#include <complex>

#include <cmath>

#include <algorithm>

#include <vector>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <numeric>

#include <sstream>

#include <ctime>

#include <cctype>

#include <set>

#include <map>

#include <queue>

#include <bitset>

#include <deque>

#include <stack>

#include <memory.h>

using namespace std;

#define ll long long 

#define mp make_pair

deque<pair<int,int> > q;

bool vis[100005];

int k,ans=0; 

int main()

{

	cin>>k;

	q.push_front(mp(1,1));

	while(!q.empty()){

		pair<int,int> x=q.front();

		q.pop_front();

		if(x.first==0){

			cout<<ans+x.second;

			return 0;

		}

		if(vis[x.first]){

			continue;

		}

		vis[x.first]=1;

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

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

	}

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int e[100009],k;

typedef pair<int,int> P;

deque<P>q;

int main(){scanf("%d",&k);

    memset(e,0,sizeof(e));q.push_back(make_pair(1,1));

    while(!q.empty()){P x=q.front();q.pop_front();

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

     if(x.first==0){printf("%d\n",x.second);break;}

     q.push_front(make_pair(x.first*10%k,x.second));

     q.push_back(make_pair((x.first+1)%k,x.second+1));

    }return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<int,int> P;

const int maxn=2e5+100;

int k;

bool vis[maxn];

 

int main()

{

    //freopen("1.txt","r",stdin);

    while (scanf("%d",&k)!=EOF)

    {

        memset(vis,0,sizeof(vis));

        deque<P> q;

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

        while (!q.empty())

        {

            auto t=q.front(); q.pop_front();

            if (vis[t.first]) continue;

            vis[t.first]=1;

            if (t.first==0)

            {

                printf("%d\n",t.second);

                break;

            }

            q.push_front(make_pair(t.first*10%k,t.second));

            q.push_back(make_pair((t.first+1)%k,t.second+1));

        }

    }

    return 0;

}

// Fastest known solution for this problem: