stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 1.313259207478357x):
// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define N 100005

#define mp make_pair

#define pr pair<int,int>

#define fr first

#define sd second

using namespace std;

const int INF=2e9;

int K,h[N],e_tot=0,d[N]; bool done[N];

struct E{ int to,nex,w; }e[N<<1];

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

	e[++e_tot]=(E){v,h[u],w}; h[u]=e_tot;

}

void Dijkstra(int s){

	for(int i=0;i<K;++i) d[i]=INF,done[i]=0;

	priority_queue<pr> Q; d[s]=0; Q.push(mp(-d[s],s));

	while(!Q.empty()){

		pr x=Q.top(); Q.pop(); int u=x.sd;

		if(done[u]) continue; done[u]=1;

		for(int i=h[u],v;i;i=e[i].nex){

			v=e[i].to;

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

				d[v]=d[u]+e[i].w; Q.push(mp(-d[v],v));

			}

		}

	}

}

int main(){

	scanf("%d",&K);

	for(int i=0,nex;i<K;++i){

		nex=(i+1)%K; add(i,nex,1);

	}

	for(int i=0,nex;i<K;++i){

		nex=i*10%K; add(i,nex,0);

	}

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

	return 0;

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

}

// Faster C++ solution for the same problem (measured speedup: 1.3746892210112718x):
// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define N 100005

#define mp make_pair

#define pr pair<int,int>

#define fr first

#define sd second

using namespace std;

const int INF=2e9;

int K,h[N],e_tot=0,d[N]; bool done[N];

struct E{ int to,nex,w; }e[N<<1];

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

	e[++e_tot]=(E){v,h[u],w}; h[u]=e_tot;

}

void Dijkstra(int s){

	for(int i=0;i<K;++i) d[i]=INF,done[i]=0;

	priority_queue<pr> Q; d[s]=0; Q.push(mp(-d[s],s));

	while(!Q.empty()){

		pr x=Q.top(); Q.pop(); int u=x.sd;

		if(done[u]) continue; done[u]=1;

		for(int i=h[u],v;i;i=e[i].nex){

			v=e[i].to;

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

				d[v]=d[u]+e[i].w; Q.push(mp(-d[v],v));

			}

		}

	}

}

int main(){

	scanf("%d",&K);

	for(int i=0,nex;i<K;++i){

		nex=(i+1)%K; add(i,nex,1);

	}

	for(int i=0,nex;i<K;++i){

		nex=i*10%K; add(i,nex,0);

	}

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

	return 0;

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

}

// Faster C++ solution for the same problem (measured speedup: 1.681037699775387x):
// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define N 100005

#define mp make_pair

#define pr pair<int,int>

#define fr first

#define sd second

using namespace std;

const int INF=2e9;

int K,h[N],e_tot=0,d[N]; bool done[N];

struct E{ int to,nex,w; }e[N<<1];

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

	e[++e_tot]=(E){v,h[u],w}; h[u]=e_tot;

}

void Dijkstra(int s){

	for(int i=0;i<K;++i) d[i]=INF,done[i]=0;

	priority_queue<pr> Q; d[s]=0; Q.push(mp(-d[s],s));

	while(!Q.empty()){

		pr x=Q.top(); Q.pop(); int u=x.sd;

		if(done[u]) continue; done[u]=1;

		for(int i=h[u],v;i;i=e[i].nex){

			v=e[i].to;

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

				d[v]=d[u]+e[i].w; Q.push(mp(-d[v],v));

			}

		}

	}

}

int main(){

	scanf("%d",&K);

	for(int i=0,nex;i<K;++i){

		nex=(i+1)%K; add(i,nex,1);

	}

	for(int i=0,nex;i<K;++i){

		nex=i*10%K; add(i,nex,0);

	}

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

	return 0;

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

}

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

using namespace std;

#define int long long

inline int read() {

	int x(0),neg(1);char ch(getchar());

	while(!isdigit(ch)) {

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

		ch=getchar();

	}

	while(isdigit(ch)) {

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*neg;

}

int vis[100005];

int n;

deque<pair<int,int> > q;

signed main() {

    n=read();

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

    while(!q.empty()) {

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

        q.pop_front();

        if(!vis[p.first]) {

            vis[p.first]=1;

            if(p.first==0) {

                printf("%lld\n",p.second);

                break;

            }

            q.push_front(make_pair((p.first*10)%n,p.second));

            q.push_back(make_pair((p.first+1)%n,p.second+1));

        }

    }

    return 0;

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

}

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

using namespace std;

#define int long long

inline int read() {

	int x(0),neg(1);char ch(getchar());

	while(!isdigit(ch)) {

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

		ch=getchar();

	}

	while(isdigit(ch)) {

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*neg;

}

int vis[100005];

int n;

deque<pair<int,int> > q;

signed main() {

    n=read();

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

    while(!q.empty()) {

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

        q.pop_front();

        if(!vis[p.first]) {

            vis[p.first]=1;

            if(p.first==0) {

                printf("%lld\n",p.second);

                break;

            }

            q.push_front(make_pair((p.first*10)%n,p.second));

            q.push_back(make_pair((p.first+1)%n,p.second+1));

        }

    }

    return 0;

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

}

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

using namespace std;

#define int long long

inline int read() {

	int x(0),neg(1);char ch(getchar());

	while(!isdigit(ch)) {

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

		ch=getchar();

	}

	while(isdigit(ch)) {

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*neg;

}

int vis[100005];

int n;

deque<pair<int,int> > q;

signed main() {

    n=read();

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

    while(!q.empty()) {

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

        q.pop_front();

        if(!vis[p.first]) {

            vis[p.first]=1;

            if(p.first==0) {

                printf("%lld\n",p.second);

                break;

            }

            q.push_front(make_pair((p.first*10)%n,p.second));

            q.push_back(make_pair((p.first+1)%n,p.second+1));

        }

    }

    return 0;

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

}

// Faster C++ solution for the same problem (measured speedup: 2.1423763094574073x):
//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; 

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

}

// Faster C++ solution for the same problem (measured speedup: 2.3190953890344526x):
//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; 

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

}

// Faster C++ solution for the same problem (measured speedup: 2.835904085633488x):
//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; 

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

}

// Faster C++ solution for the same problem (measured speedup: 4.328792193208178x):
//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; 

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

}

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

#include <cstdio>

#include <queue>

#include <cstring>



char buf[1<<21], *p1, *p2;

#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin)), p1 == p2 ? EOF : *p1++)

#define lint long long

#define pii pair<int, int>

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

#define isnum(x) ('0' <= (x) && (x) <= '9')

template<typename tint>

inline void readint(tint& x) {

	int f = 1; char ch = getc(); x = 0;

	for(; !isnum(ch); ch = getc()) if(ch == '-') f = -1;

	for(; isnum(ch); ch = getc()) x = x * 10 + ch - '0';

	x *= f;

}

using namespace std;

const int maxn = 1e5 + 10;



// 倍数问题扩展到剩余系下考虑

int n;



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

int dist[maxn];



void dijkstra() {

	memset(dist, 0x3f, sizeof(int) * n);

	dist[1] = 1, q.push(mp(dist[1], 1));

	while(!q.empty()) {

		pii now = q.top(); q.pop();

		if(now.second > dist[now.first]) continue;

		int x = now.first;



		int y = (x * 10) % n;

		if(dist[y] > dist[x]) dist[y] = dist[x], q.push(mp(y, dist[y]));

		y = (x + 1) % n;

		if(dist[y] > dist[x] + 1) dist[y] = dist[x] + 1, q.push(mp(y, dist[y]));

	}

}



int main() {

	readint(n);

	dijkstra();

	cout << dist[0] << endl;

	return 0;

}