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

}

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

#define maxn 2000010

#define inf 1000000000

using namespace std;

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;

}

int k;

int dis[maxn];

bool vis[maxn];

struct edge

{

    int to,nxt,v;

}e[maxn];

int head[maxn],edge_cnt;

void add(int from,int to,int val)

{

    e[++edge_cnt]=(edge){to,head[from],val};

    head[from]=edge_cnt;

}

struct node

{

    int val,num;

};

bool operator <(const node &x,const node &y)

{

    return x.val>y.val;

}

void dijkstra()

{

    priority_queue<node> q;

    for(int i=0;i<=k;++i) dis[i]=inf;

    dis[1]=1,q.push((node){1,1});

    while(!q.empty())

    {

        int x=q.top().num;

        q.pop();

        if(vis[x]) continue;

        vis[x]=true;

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

        {

            int y=e[i].to,v=e[i].v;

            if(dis[y]>dis[x]+v)

                dis[y]=dis[x]+v,q.push((node){dis[y],y});

        }

    }

}

int main()

{

    read(k);

    for(int i=1;i<k;++i) add(i,i*10%k,0),add(i,(i+1)%k,1);

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

    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.0727282555289874x):
#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)

*/
// 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.2351766772917783x):
#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)

*/
// 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.733284150887624x):
#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)

*/
// 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.323100513742981x):
#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)

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

}

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

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

}


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

}

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

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

#define reg register

typedef long long ll;

const int MN=2e5;

struct edge{int t,nxt,c;}es[(MN<<1)+5];

int h[MN+5],cnt;

inline void ins(int s,int t,int c){es[++cnt]=(edge){t,h[s],c};h[s]=cnt;}

int dis[MN+5],q[MN+5],he,ta;

bool inq[MN];

inline void SPFA(){

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

	he=ta=0;q[ta++]=inq[1]=dis[1]=1;

	while(he!=ta){

		reg int v=q[he++];he%=MN;

		for(reg int i=h[v];~i;i=es[i].nxt)

			if(dis[es[i].t]>dis[v]+es[i].c){

				dis[es[i].t]=dis[v]+es[i].c;

				if(!inq[es[i].t]){

					inq[es[i].t]=1;

					if(dis[es[i].t]<dis[q[he]])he=(he-1)%MN,q[he]=es[i].t;

					else q[ta++]=es[i].t,ta%=MN;

				}

			}

		inq[v]=0;

	}

}

int main(){

	memset(h,-1,sizeof(h));int k;scanf("%d",&k);

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

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

	}

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

    return 0;

}

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

}
// Slower C++ solution:
/*

 * 很神奇的一道题目

 * 求出k的倍数的正数x，使得x的位数和最小。

 * eg k = 6 x = 12(位数和为3) x = 30(位数和为3)

 * 

 * 考虑正数x 其变为 x+1 需要代价1.

 *    正数x 变成 x*10 需要代价0.

 * 由于我们只需要得到k的倍数，也就是说在 %k 意义下为0的点。

 * 所以只有[0,k-1]k点。对每个点建立两条边，分别为(x+1)%k 和 (x*10)%k

 */

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

const int inf = 0x3f3f3f3f;

struct Edge {

    int to,val;

    Edge(){}

    Edge(int _t,int _v){to = _t;val = _v;}

};

struct qNode {

    int u,val;

    qNode(){}

    qNode(int _u,int _v) {u = _u;val = _v;}

    bool operator < (const qNode &a) const{

        return val > a.val;

    }

};

vector<Edge> ways[maxn];

int dist[maxn];

bool vis[maxn];

int n;

inline void init() {

    for(int i=0;i<maxn;i++) ways[i].clear();

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

    memset(dist,inf,sizeof(dist));

}

inline void addedge(int from,int to,int val) {

    ways[from].push_back(Edge(to,val));

}

int solve(int from,int to) {

    priority_queue<qNode> qu;

    dist[from] = 1;

    qu.push(qNode(from,1));

    qNode now;

    while(!qu.empty()) {

        now = qu.top();qu.pop();

        int u = now.u;

        if(vis[u]) continue;

        vis[u] = true;

        for(auto tmp:ways[u]) {

            int v = tmp.to,cost = tmp.val;

            if(!vis[v] && dist[v] > dist[u]+cost) {

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

                qu.push(qNode(v,dist[v]));

            }

        }

    }

    return dist[to];

}

int main()

{

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

        init();

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

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

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

        }

        int ans = solve(1,0);

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

    }

    return 0;

}

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

}