stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:


#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<iostream>

#include<cstring>

#define ll long long

#define maxn 100005

			 

#define p 1000000007

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

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

using namespace std;

inline int read(){char c=getchar();int f=1;int ans = 0;while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c<='9'&&c>='0'){ans =ans*10+c-'0';c=getchar();}return ans*f;}

//_____________________________________________________________________________________________________

deque<int>q;

int vis[maxn],dis[maxn];

int main()

{

	int k = read();

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

	dis[1] = 1;

	q.push_back(1);

	while(!q.empty() )

	{

		int x = q.front() ; 

		q.pop_front() ;

		if(vis[x])

			continue;

		vis[x] = 1;

		if(dis[x*10%k]>dis[x])

		{

			dis[x*10%k] = dis[x];

			q.push_front(x*10%k);

		}

		if( dis[(x+1)%k]>dis[x] + 1 )

		{

			dis[(x+1)%k] = dis[x] + 1;

			q.push_back((x+1)%k);

		}

	}

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

    return 0;

}




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

using namespace std;

typedef long long LL;

bool vis[100005];

LL k;

deque<pair<LL, LL> > dq;

int main()

{

	cin >> k;

	dq.push_back(make_pair(1, 1));

	while(!dq.empty())

	{

		pair<LL, LL> x = dq.front(); dq.pop_front();

		if(!x.first) { cout << x.second << endl; return 0; }

		if(vis[x.first]) continue; vis[x.first] = true;

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

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

	}

	return 0;

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

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define rep(i,s,n)for(int i = s;i<n;i++)

#define repe(i,s,n)for(int i = s;i<=n;i++)

typedef long long ll;

static const ll MOD = 1e9 + 7;

static const ll INF = (ll)1 << 62;



static const int MAX = 100001;

static const int WHITE = 0;

static const int GRAY = 1;

static const int BLACK = 2;

vector<pair<int, int>> adj[MAX];



ll pre[MAX];

ll p[MAX];

ll d[MAX];

ll color[MAX];

priority_queue<pair<int, int>>PQ;

ll n;

void dijkstra(int s) {

	rep(i, 0, n) {

		d[i] = INF;

		pre[i] = INF;

		color[i] = WHITE;

	}



	d[s] = 0;

	p[s] = -1;

	PQ.push(make_pair(s, s)); // ?reverse?

	color[s] = GRAY;



	while (!PQ.empty()) {

		pair<ll, ll> f = PQ.top(); PQ.pop();

		ll u = f.second;



		color[u] = BLACK;



		if (d[u] < f.first * (-1)) continue;



		rep(j, 0, adj[u].size()) {

			ll v = adj[u][j].first;

			if (color[v] == BLACK) continue;

			if (d[v] > d[u] + adj[u][j].second) {

				d[v] = d[u] + adj[u][j].second;

				PQ.push(make_pair(d[v] * (-1), v));

				p[v] = u;

				color[v] = GRAY;

			}

		}

	}

	//rep(i, 0, n) cout << i << " " << (d[i] == INF ? -1 : d[i]) << endl;

	//rep(i, 0, n) cout << i << " " << (p[i] == INF ? -1 : p[i]) << endl;

}



vector<ll> get_path(int t) {

	vector<ll> path;

	for (; t != -1; t = p[t])path.push_back(t);

	reverse(path.begin(), path.end());

	return path;

}



int main()

{

	cin >> n;

	rep(i, 0, n) {

		adj[i].push_back(make_pair((i + 1) % n, 1));

		adj[i].push_back(make_pair((i * 10) % n, 0));

	}



	dijkstra(1);



	cout << d[0] + 1 << endl;

	return 0;

}


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

#include<fstream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<set>

#include<deque>

#include<stack>

#include<string>

#include<cstring>

#include<map>

using namespace std;

int k;

struct pa{

    int x,y;

};

deque<pa>p;

bool vis[10000000];

void bfs(){

    while(p.size())

    {

        pa n=p.front();p.pop_front();

        if(vis[n.x])

        {

            continue;

        }

        vis[n.x]=1;

        if(!n.x)

        {

            cout<<n.y;

            return;

        }

        pa a;

        a.x=n.x*10%k;a.y=n.y;

        p.push_front(a);

        a.x=(n.x+1)%k;a.y=n.y+1;

        p.push_back(a);

    }

}

int read()

{

    int x=0,f=1;

    char ch;

    while((ch=getchar())<'0'||ch>'9')

    {

        if(ch=='-')

        {

            x=-1;

        }

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*f;

}

int main()

{

    k=read();

    pa b;

    b.x=1;b.y=1;

    p.push_front(b);

    bfs();

    return 0;

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

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<deque>

using namespace std;

#define ll long long

#define rg register

#define inf 0x3f3f3f3f

#define MX 100005

#define fi first

#define se second

typedef pair<int,int> PA;

deque<PA> que;

int dis[MX];

int n;

int main(){



    scanf("%d",&n);

    memset(dis,inf,sizeof(dis));

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

    while(1)

    {

        PA x=que.front();que.pop_front();

        if(dis[x.fi]<=x.se) continue;

        else dis[x.fi]=x.se;

        if(x.fi==0) break;

        if(x.fi%10!=9) que.push_back(make_pair(x.fi==n-1?0:x.fi+1,x.se+1));

        que.push_front(make_pair(x.fi*10%n,x.se));

    }

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

    return 0;

}

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

#include<fstream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<set>

#include<deque>

#include<stack>

#include<string>

#include<cstring>

#include<map>

using namespace std;

int k;

struct pa{

    int x,y;

};

deque<pa>p;

bool vis[10000000];

void bfs(){

    while(p.size())

    {

        pa n=p.front();p.pop_front();

        if(vis[n.x])

        {

            continue;

        }

        vis[n.x]=1;

        if(!n.x)

        {

            cout<<n.y;

            return;

        }

        pa a;

        a.x=n.x*10%k;a.y=n.y;

        p.push_front(a);

        a.x=(n.x+1)%k;a.y=n.y+1;

        p.push_back(a);

    }

}

int read()

{

    int x=0,f=1;

    char ch;

    while((ch=getchar())<'0'||ch>'9')

    {

        if(ch=='-')

        {

            x=-1;

        }

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*f;

}

int main()

{

    k=read();

    pa b;

    b.x=1;b.y=1;

    p.push_front(b);

    bfs();

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



const int maxn=2e5+10;

int head[maxn],dis[maxn],vis[maxn],num;

struct Le

{

	int nt,to,dis;

}edge[maxn];



void add(int f,int t,int d){

	edge[++num].nt=head[f];

	edge[num].to=t;

	edge[num].dis=d;

	head[f]=num;

} 



int k;



void spfa(int s) {

	queue<int> q;

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

	dis[s]=1;

	q.push(s);

	vis[s]=1;

	while(!q.empty()) {

		int u=q.front();

		q.pop();vis[u]=0;

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

			int v=edge[i].to;

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

				dis[v]=dis[u]+edge[i].dis;

				if(!vis[v]) {

					q.push(v);

					vis[v]=1;

				}

			}

		}

	}

}



int main() {

	scanf("%d",&k);

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

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

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

	}

	spfa(1);

	cout<<dis[0]<<"\n";

	return 0;

}


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

#include<fstream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<set>

#include<deque>

#include<stack>

#include<string>

#include<cstring>

#include<map>

using namespace std;

int k;

struct pa{

    int x,y;

};

deque<pa>p;

bool vis[10000000];

void bfs(){

    while(p.size())

    {

        pa n=p.front();p.pop_front();

        if(vis[n.x])

        {

            continue;

        }

        vis[n.x]=1;

        if(!n.x)

        {

            cout<<n.y;

            return;

        }

        pa a;

        a.x=n.x*10%k;a.y=n.y;

        p.push_front(a);

        a.x=(n.x+1)%k;a.y=n.y+1;

        p.push_back(a);

    }

}

int read()

{

    int x=0,f=1;

    char ch;

    while((ch=getchar())<'0'||ch>'9')

    {

        if(ch=='-')

        {

            x=-1;

        }

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*f;

}

int main()

{

    k=read();

    pa b;

    b.x=1;b.y=1;

    p.push_front(b);

    bfs();

    return 0;

}
// Slower C++ solution:


#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<iostream>

#include<cstring>

#define ll long long

#define maxn 100005

			 

#define p 1000000007

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

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

using namespace std;

inline int read(){char c=getchar();int f=1;int ans = 0;while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c<='9'&&c>='0'){ans =ans*10+c-'0';c=getchar();}return ans*f;}

//_____________________________________________________________________________________________________

deque<int>q;

int vis[maxn],dis[maxn];

int main()

{

	int k = read();

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

	dis[1] = 1;

	q.push_back(1);

	while(!q.empty() )

	{

		int x = q.front() ; 

		q.pop_front() ;

		if(vis[x])

			continue;

		vis[x] = 1;

		if(dis[x*10%k]>dis[x])

		{

			dis[x*10%k] = dis[x];

			q.push_front(x*10%k);

		}

		if( dis[(x+1)%k]>dis[x] + 1 )

		{

			dis[(x+1)%k] = dis[x] + 1;

			q.push_back((x+1)%k);

		}

	}

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

    return 0;

}




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

#include<fstream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<queue>

#include<set>

#include<deque>

#include<stack>

#include<string>

#include<cstring>

#include<map>

using namespace std;

int k;

struct pa{

    int x,y;

};

deque<pa>p;

bool vis[10000000];

void bfs(){

    while(p.size())

    {

        pa n=p.front();p.pop_front();

        if(vis[n.x])

        {

            continue;

        }

        vis[n.x]=1;

        if(!n.x)

        {

            cout<<n.y;

            return;

        }

        pa a;

        a.x=n.x*10%k;a.y=n.y;

        p.push_front(a);

        a.x=(n.x+1)%k;a.y=n.y+1;

        p.push_back(a);

    }

}

int read()

{

    int x=0,f=1;

    char ch;

    while((ch=getchar())<'0'||ch>'9')

    {

        if(ch=='-')

        {

            x=-1;

        }

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-48;

        ch=getchar();

    }

    return x*f;

}

int main()

{

    k=read();

    pa b;

    b.x=1;b.y=1;

    p.push_front(b);

    bfs();

    return 0;

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

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

#define rep(i,s,n)for(int i = s;i<n;i++)

#define repe(i,s,n)for(int i = s;i<=n;i++)

typedef long long ll;

static const ll MOD = 1e9 + 7;

static const ll INF = (ll)1 << 62;



static const int MAX = 100001;

static const int WHITE = 0;

static const int GRAY = 1;

static const int BLACK = 2;

vector<pair<int, int>> adj[MAX];



ll pre[MAX];

ll p[MAX];

ll d[MAX];

ll color[MAX];

priority_queue<pair<int, int>>PQ;

ll n;

void dijkstra(int s) {

	rep(i, 0, n) {

		d[i] = INF;

		pre[i] = INF;

		color[i] = WHITE;

	}



	d[s] = 0;

	p[s] = -1;

	PQ.push(make_pair(s, s)); // ?reverse?

	color[s] = GRAY;



	while (!PQ.empty()) {

		pair<ll, ll> f = PQ.top(); PQ.pop();

		ll u = f.second;



		color[u] = BLACK;



		if (d[u] < f.first * (-1)) continue;



		rep(j, 0, adj[u].size()) {

			ll v = adj[u][j].first;

			if (color[v] == BLACK) continue;

			if (d[v] > d[u] + adj[u][j].second) {

				d[v] = d[u] + adj[u][j].second;

				PQ.push(make_pair(d[v] * (-1), v));

				p[v] = u;

				color[v] = GRAY;

			}

		}

	}

	//rep(i, 0, n) cout << i << " " << (d[i] == INF ? -1 : d[i]) << endl;

	//rep(i, 0, n) cout << i << " " << (p[i] == INF ? -1 : p[i]) << endl;

}



vector<ll> get_path(int t) {

	vector<ll> path;

	for (; t != -1; t = p[t])path.push_back(t);

	reverse(path.begin(), path.end());

	return path;

}



int main()

{

	cin >> n;

	rep(i, 0, n) {

		adj[i].push_back(make_pair((i + 1) % n, 1));

		adj[i].push_back(make_pair((i * 10) % n, 0));

	}



	dijkstra(1);



	cout << d[0] + 1 << endl;

	return 0;

}


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

#include <cstdio>

#include <deque>

#define int long long

using namespace std;

bool vis[100005];

signed main() {

	int n; cin >> n;

	deque<pair<int, int> > q; q.push_front(make_pair(1, 1));

	while (!q.empty()) {

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

		if (vis[p.first]) continue; vis[p.first] = 1;

		if (!p.first) { cout << p.second << endl; return 0; }

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

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<deque>

using namespace std;

#define ll long long

#define rg register

#define inf 0x3f3f3f3f

#define MX 100005

#define fi first

#define se second

typedef pair<int,int> PA;

deque<PA> que;

int dis[MX];

int n;

int main(){



    scanf("%d",&n);

    memset(dis,inf,sizeof(dis));

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

    while(1)

    {

        PA x=que.front();que.pop_front();

        if(dis[x.fi]<=x.se) continue;

        else dis[x.fi]=x.se;

        if(x.fi==0) break;

        if(x.fi%10!=9) que.push_back(make_pair(x.fi==n-1?0:x.fi+1,x.se+1));

        que.push_front(make_pair(x.fi*10%n,x.se));

    }

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

    return 0;

}

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

#include <cstdio>

#include <deque>

#define int long long

using namespace std;

bool vis[100005];

signed main() {

	int n; cin >> n;

	deque<pair<int, int> > q; q.push_front(make_pair(1, 1));

	while (!q.empty()) {

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

		if (vis[p.first]) continue; vis[p.first] = 1;

		if (!p.first) { cout << p.second << endl; return 0; }

		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;



const int maxn=2e5+10;

int head[maxn],dis[maxn],vis[maxn],num;

struct Le

{

	int nt,to,dis;

}edge[maxn];



void add(int f,int t,int d){

	edge[++num].nt=head[f];

	edge[num].to=t;

	edge[num].dis=d;

	head[f]=num;

} 



int k;



void spfa(int s) {

	queue<int> q;

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

	dis[s]=1;

	q.push(s);

	vis[s]=1;

	while(!q.empty()) {

		int u=q.front();

		q.pop();vis[u]=0;

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

			int v=edge[i].to;

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

				dis[v]=dis[u]+edge[i].dis;

				if(!vis[v]) {

					q.push(v);

					vis[v]=1;

				}

			}

		}

	}

}



int main() {

	scanf("%d",&k);

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

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

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

	}

	spfa(1);

	cout<<dis[0]<<"\n";

	return 0;

}


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

#include <cstdio>

#include <deque>

#define int long long

using namespace std;

bool vis[100005];

signed main() {

	int n; cin >> n;

	deque<pair<int, int> > q; q.push_front(make_pair(1, 1));

	while (!q.empty()) {

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

		if (vis[p.first]) continue; vis[p.first] = 1;

		if (!p.first) { cout << p.second << endl; return 0; }

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

#include<algorithm>

#include<queue>

#include<cmath>

#include<iostream>

#include<cstring>

#define ll long long

#define maxn 100005

			 

#define p 1000000007

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

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

using namespace std;

inline int read(){char c=getchar();int f=1;int ans = 0;while(c>'9'||c<'0'){if(c=='-')f=-f;c=getchar();}while(c<='9'&&c>='0'){ans =ans*10+c-'0';c=getchar();}return ans*f;}

//_____________________________________________________________________________________________________

deque<int>q;

int vis[maxn],dis[maxn];

int main()

{

	int k = read();

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

	dis[1] = 1;

	q.push_back(1);

	while(!q.empty() )

	{

		int x = q.front() ; 

		q.pop_front() ;

		if(vis[x])

			continue;

		vis[x] = 1;

		if(dis[x*10%k]>dis[x])

		{

			dis[x*10%k] = dis[x];

			q.push_front(x*10%k);

		}

		if( dis[(x+1)%k]>dis[x] + 1 )

		{

			dis[(x+1)%k] = dis[x] + 1;

			q.push_back((x+1)%k);

		}

	}

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

    return 0;

}




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

#include <cstdio>

#include <deque>

#define int long long

using namespace std;

bool vis[100005];

signed main() {

	int n; cin >> n;

	deque<pair<int, int> > q; q.push_front(make_pair(1, 1));

	while (!q.empty()) {

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

		if (vis[p.first]) continue; vis[p.first] = 1;

		if (!p.first) { cout << p.second << endl; return 0; }

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

#include<cstdio>

#include<algorithm>

#include<vector>

#include<utility>

#include<cstring>

#include<queue>

#define maxn 100000 

using namespace std;

int dist[maxn+5];

bool inq[maxn+5];

vector<pair<int,int> >E[maxn+5];

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

	E[u].push_back(make_pair(v,w));

}

int spfa(int s,int t){

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

	queue<int>q;

	q.push(s);

	dist[s]=1;

	inq[s]=1;

	while(!q.empty()){

		int x=q.front();

		q.pop();

		inq[x]=0;

		for(auto p : E[x]){

			int w=p.second,y=p.first;

			if(dist[y]>dist[x]+w){

				dist[y]=dist[x]+w;

				if(!inq[y]){

					inq[y]=1;

					q.push(y);

				}

			}

		}

	}

	return dist[t];

}

int K;

int main(){



	scanf("%d",&K);

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

		add_edge(i,(i+1)%K,1);//如果没有进位,数位和+1 

		add_edge(i,i*10%K,0);

	}

	printf("%d\n",spfa(1,0));//从1到%K=0(实际上就是K) 

	

}


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

#include <cstdio>

#include <deque>

#define int long long

using namespace std;

bool vis[100005];

signed main() {

	int n; cin >> n;

	deque<pair<int, int> > q; q.push_front(make_pair(1, 1));

	while (!q.empty()) {

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

		if (vis[p.first]) continue; vis[p.first] = 1;

		if (!p.first) { cout << p.second << endl; return 0; }

		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;

#define IL inline

#define RI register int

typedef long long LL;

const int MAXN = 1000005;

struct node{int from, to, w;} G[MAXN];

int dist[MAXN];

int head[MAXN];

bool vis[MAXN];

int cnt,k;

IL void add(int u, int v, int w)

{

    G[++cnt].to=v;

    G[cnt].w=w;

    G[cnt].from=head[u];

    head[u]=cnt;

}

IL void spfa(int s)

{

    memset(dist,127,sizeof(dist));

    memset(vis, false, sizeof(vis));

    queue<int> q;

    while(!q.empty())

        q.pop();

    vis[1]=true;

    q.push(s);

    dist[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=false;

        for(RI i=head[u]; i; i=G[i].from)

        {

            int v=G[i].to;

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

            {

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

                if(!vis[v])

                {

                    vis[v]=true;

                    q.push(v);

                }

            }

        }

    }

}

int main()

{

    std::cin>>k;

    for(RI i=0; i<k; ++i)

    {

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

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

    }

    spfa(1);

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

    return 0;

}

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

#include<queue>

#include<vector>

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



using namespace std;

const int SIZE=1e6;

deque< pair<int,int> > p;

bool vis[SIZE];

int k;



void bfs() {

	while(p.size()) {

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

		if(vis[now.first]) continue;

		vis[now.first]=true;

		if(!now.first) {

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

			return;

		}

		p.push_front(put(now.first*10%k,now.second));

		p.push_back(put((now.first+1)%k,now.second+1));

	}

	

}

int main() {

	scanf("%d",&k);

	p.push_front(put(1,1));

	bfs();

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define IL inline

#define RI register int

typedef long long LL;

const int MAXN = 1000005;

struct node{int from, to, w;} G[MAXN];

int dist[MAXN];

int head[MAXN];

bool vis[MAXN];

int cnt,k;

IL void add(int u, int v, int w)

{

    G[++cnt].to=v;

    G[cnt].w=w;

    G[cnt].from=head[u];

    head[u]=cnt;

}

IL void spfa(int s)

{

    memset(dist,127,sizeof(dist));

    memset(vis, false, sizeof(vis));

    queue<int> q;

    while(!q.empty())

        q.pop();

    vis[1]=true;

    q.push(s);

    dist[s]=0;

    while(!q.empty())

    {

        int u=q.front();

        q.pop();

        vis[u]=false;

        for(RI i=head[u]; i; i=G[i].from)

        {

            int v=G[i].to;

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

            {

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

                if(!vis[v])

                {

                    vis[v]=true;

                    q.push(v);

                }

            }

        }

    }

}

int main()

{

    std::cin>>k;

    for(RI i=0; i<k; ++i)

    {

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

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

    }

    spfa(1);

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

    return 0;

}

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

#include<queue>

#include<cstring>

#include<utility>

using namespace std;

const int N = 100010;

const int M = N << 1;

int dis[N];

int k;

int tot, head[N], pre[M], ver[M], val[M];

int vis[N];

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

  ver[++tot] = y, val[tot] = z, pre[tot] = head[x], head[x] = tot;

}

void build() {

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

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

  }

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

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

  }



}

int main() {

  scanf("%d", &k);

  build();

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

  priority_queue< pair<int, int> > q;

  q.push(make_pair(-1, 1));

  dis[1] = 1;

  while(!q.empty()) {

    int x = q.top().second; q.pop();

    if(vis[x]) continue;

    vis[x] = 1;

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

      int y = ver[i], v = val[i];

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

	dis[y] = dis[x] + v;

	q.push(make_pair(-dis[y], y));

      }

    }

  }

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

  return 0;

}