stablegradients/pie-gem5-pairs huggingface dataset:
// 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.2682396792860025x):
#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;

}
// 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.6223878093933142x):
#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;

}
// 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: 3.3566896327132327x):
#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;

}
// 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.3408976736370162x):
#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);

}
// 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.6397157309975405x):
#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);

}
// 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: 3.0500377794389384x):
#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);

}
// 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.4574896253786915x):
#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>

#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.5392929537145739x):
#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 <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.8823232528798532x):
#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;



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

}