stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

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

#define RREP(i,a,b) for(int i=(a);i>=(b);i--)

#define pq priority_queue

#define P pair<ll,ll>

#define P2 pair<int,P>

#define P3 pair<int,P2>

typedef long long ll; typedef long double ld;

using namespace std;

const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};

const ll LINF=1e18;

const ld PI=abs(acos(-1));

int k;

vector<P> g[100010];



ll dijkstra(int s, int t){

	ll min_cost[100010]={};

	pq<P, vector<P>, greater<P>> que;

	REP(i,0,k) min_cost[i]=INF;

	que.emplace(0,s);

	min_cost[s]=0;

	while(!que.empty()){

		auto p=que.top(); que.pop();

		if(p.first>min_cost[p.second]) continue;



		for(auto e:g[p.second]){

			if(p.first+e.second>=min_cost[e.first]) continue;

			min_cost[e.first]=p.first+e.second;

			que.emplace(min_cost[e.first], e.first);

		}

	}



	return min_cost[t];

}



int main(){

	cin >> k;

	REP(i,0,k) g[i].push_back(P((i*10)%k,0)),g[i].push_back(P((i+1)%k,1));

	

	cout << dijkstra(1,0)+1 << endl;

	return 0;

}


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

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

#define RREP(i,a,b) for(int i=(a);i>=(b);i--)

#define pq priority_queue

#define P pair<int,int>

#define P2 pair<int,P>

#define P3 pair<int,P2>

typedef long long ll; typedef long double ld;

using namespace std;

const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};

const ll LINF=1e18;

const ld PI=abs(acos(-1));



vector<P> g[100010];

int n;



int solve(){

	int min_cost[100010]; REP(i,0,n) min_cost[i] = INF;

	deque<P> qu; qu.push_front({1,1}); min_cost[1] = 0;

	

	while(!qu.empty()){

		auto p = qu.front(); qu.pop_front();

		

		for(auto e:g[p.second]){

			if(p.first + e.second >= min_cost[e.first]) continue;

			min_cost[e.first] = p.first + e.second;

			

			if(e.second) qu.push_back({min_cost[e.first], e.first});

			else qu.push_front({min_cost[e.first], e.first});

		}

	}

	

	return min_cost[0];

}



int main(){

	cin >> n;

	

	REP(i,0,n){

		g[i].push_back({(i+1)%n, 1});

		g[i].push_back({(i*10)%n, 0});

	}

	

	cout << solve() << endl;

	return 0;

}


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

#define maxn 100005

#define ll long long

using namespace std;

int k;

int dis[maxn];

struct edge

{

	int v,w;

	edge(int v=0,int w=0):v(v),w(w){}

};

vector<edge>adj[maxn];

bool vis[maxn];

void bfs()

{

	queue<int>q;

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

	dis[1]=1;vis[1]=true;

	q.push(1);

	int u,v,w;

	while(!q.empty())

	{

		u=q.front();

		q.pop();

		vis[u]=0;

		int sz=adj[u].size();

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

		{

			v=adj[u][i].v;

			w=adj[u][i].w;

			if(dis[u]+w<dis[v])

			{

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

				if(!vis[v])

				{

					vis[v]=1;

					q.push(v);

				}

			}

		}

	}

}

int main()

{

	scanf("%d",&k);

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

	{

		adj[i].push_back(edge((i+1)%k,1));

		adj[i].push_back(edge(i*10%k,0));

	}

	bfs();

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

	return 0;

}

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

#include<cstdio>

#include<cstring>

using namespace std;

int mod,l,r,vis[100050];

struct node{

	long long tot,val;

}q[100050];

int main(){

	cin>>mod;

	q[l=r=1].tot=1;q[1].val=1;

	while(l<=r){

		

		if(!q[l].tot){

			cout<<q[l].val;return 0;

		}if(vis[q[l].tot]){

			++l;

		}else{

			vis[q[l].tot]=1;

			q[l].tot=q[l].tot*10%mod;q[l].val=q[l].val;

			q[++r].tot=(q[l].tot+1)%mod;q[r].val=q[l].val+1;

		}

	}

}

// 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 << 4];

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++)

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

	for (int i = 1; i < 10; i++) q.push(i);

	for (; !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):
#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int mod,l,r,vis[100050];

struct node{

	long long tot,val;

}q[100050];

int main(){

	cin>>mod;

	q[l=r=1].tot=1;q[1].val=1;

	while(l<=r){

		

		if(!q[l].tot){

			cout<<q[l].val;return 0;

		}if(vis[q[l].tot]){

			++l;

		}else{

			vis[q[l].tot]=1;

			q[l].tot=q[l].tot*10%mod;q[l].val=q[l].val;

			q[++r].tot=(q[l].tot+1)%mod;q[r].val=q[l].val+1;

		}

	}

}

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

using namespace std;

#define int long long

#define fi first

#define se second

#define mp make_pair

int n;

const int maxn=2e5+100;

int dist[maxn];

priority_queue < pair < int,int > > q;

bool used[maxn];

void solve(){

	cin >> n;

	memset(dist,10,sizeof(dist));

	q.push(mp(0,0));

	dist[0]=0;

	while (!q.empty()){

		int u=-q.top().fi;

		int v=q.top().se;

//		cout << u << ' '<< v << endl;

		q.pop();

		if (dist[v]!=u) continue;

		used[v]=true;

		int tmp[2];tmp[1]=(v+1-1)%n+1;

		tmp[0]=(v*10-1)%n+1;

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

			if (!used[tmp[i]] && dist[tmp[i]]>u+i){

				dist[tmp[i]]=u+i;

				q.push(mp(-dist[tmp[i]],tmp[i]));

			}

		}

	}

	cout << dist[n] << endl;

}

signed main(){

	solve();

	return 0;

}

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

#include<cstdio>

#include<cstring>

using namespace std;

int mod,l,r,vis[100050];

struct node{

	long long tot,val;

}q[100050];

int main(){

	cin>>mod;

	q[l=r=1].tot=1;q[1].val=1;

	while(l<=r){

		

		if(!q[l].tot){

			cout<<q[l].val;return 0;

		}if(vis[q[l].tot]){

			++l;

		}else{

			vis[q[l].tot]=1;

			q[l].tot=q[l].tot*10%mod;q[l].val=q[l].val;

			q[++r].tot=(q[l].tot+1)%mod;q[r].val=q[l].val+1;

		}

	}

}

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

#include <vector>

#include <queue>

#include <algorithm>

#define MAX_V 200000

#define INF 1 << 29

using namespace std;

typedef long long ll;

typedef pair<ll, int> pli;

struct Edge {

    int to;

    ll cost;

};

vector<Edge> g[MAX_V];

ll d[MAX_V];

void solve() {

    d[0] = 0;

    queue<pli> q;

    q.push(pli(0LL, 0));

    while (!q.empty()) {

        pli p = q.front(); q.pop();

        int v = p.second;

        for (size_t i = 0U; i < g[v].size(); ++i) {

            Edge e = g[v][i];

            if (d[e.to] > e.cost + d[v]) {

                d[e.to] = e.cost + d[v];

                q.push(pli(d[e.to], e.to));

            }

        }

    }

}

int main(void) {

    int k; cin >> k;

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

        d[i] = INF;

    }

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

        Edge e = { i + 1, 1LL };

        g[i].push_back(e);

    }

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

        Edge e = { i * 10 % k, 0LL };

        if (e.to == 0) e.to = k;

        g[i].push_back(e);

    }

    solve();

    cout << d[k] << endl;

    return 0;

}










































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

using namespace std;

const int INF = 1e9;

int k;

int ary[100005];

void solve(int p, int q) {

    if (ary[p] <= q) return;

    ary[p] = q;

    solve(p * 10 % k, q);

    solve((p + 1) % k, q + 1);

}

int main(void) {

    cin >> k;

    for (int i = 0; i < k; ++i) ary[i] = 45;

    solve(1, 1);

    cout << ary[0] << endl;

    return 0;

}

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

#include <cstring>

#include <sstream>

#include <algorithm>

#include <vector>

using namespace std;



#define min(a,b) (a<b?a:b)

#define mem(a,n) memset(a,sizeof(a),n)

typedef long long ll;

const int mod=1e9+7;

const int N=1e5+5;

const int INF=0x3f3f3f3f;

bool vis[N][100];



int digit_sum(int x)

{

    int sum=0;

    while(x)

    {

        sum+=(x%10);

        x/=10;

    }

    return sum;

}

int n;

void dfs(int x,int sum)

{

    if(sum>=99||vis[x][sum]) return;

    vis[x][sum]=1;

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

        dfs((10*x+i)%n,sum+i);

}



int main()

{

    while(~scanf("%d",&n))

    {

        mem(vis,0);

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

            dfs(i,digit_sum(i));

        int ans=INF;

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

            if(vis[0][i])

                ans=min(ans,i);

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

    }

    return 0;

}

/**

2

1 5

2 4

3 6

3

1 1 1

2 2 2

3 3 3

6

3 14 159 2 6 53

58 9 79 323 84 6

2643 383 2 79 50 288

**/


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

#include <cstring>

#include <sstream>

#include <algorithm>

#include <vector>

using namespace std;



#define min(a,b) (a<b?a:b)

#define mem(a,n) memset(a,sizeof(a),n)

typedef long long ll;

const int mod=1e9+7;

const int N=1e5+5;

const int INF=0x3f3f3f3f;

bool vis[N][100];



int digit_sum(int x)

{

    int sum=0;

    while(x)

    {

        sum+=(x%10);

        x/=10;

    }

    return sum;

}

int n;

void dfs(int x,int sum)

{

    if(sum>=80||vis[x][sum]) return;

    vis[x][sum]=1;

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

        dfs((10*x+i)%n,sum+i);

}



int main()

{

    while(~scanf("%d",&n))

    {

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

        mem(vis,0);

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

            dfs(i,digit_sum(i));

        int ans=INF;

       // printf("%d\n",ans);

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

            if(vis[0][i])

                ans=min(ans,i);

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

    }

    return 0;

}

/**

2

1 5

2 4

3 6

3

1 1 1

2 2 2

3 3 3

6

3 14 159 2 6 53

58 9 79 323 84 6

2643 383 2 79 50 288

**/


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

}

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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*

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;

}




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

}

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



*/

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

}

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

}

// 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<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];

}

// 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>

#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;

}

// 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 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;

}


// 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: