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


#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<queue>

using namespace std;

 

int vis[100009];

typedef pair<int, int> P;

 

 

int main()

{

    int k;

    scanf("%d", &k);

    deque<P> q;

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

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

    while(!q.empty())

    {

        P x = q.front(); q.pop_front();

        if(vis[x.first]) continue;

        vis[x.first] = 1;

        if(x.first == 0)

        {

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

            break;

        }

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

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

 

    }

    return 0;

}

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

#include<deque>

using namespace std;



int k;

bool vis[200000];

pair<int,int>p;

deque<pair<int,int>>q;



int main()

{

	cin>>k;

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

	while(q.size())

	{

		p=q.front();

		q.pop_front();

		if(vis[p.first])

			continue;

		vis[p.first]=1;

		if(p.first==0)

		{

			cout<<p.second+1;

			return 0;

		}

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

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

	}

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <vector>

#include <map>

#include <set>

#include <unordered_set>

#include <cstdlib>

#include <ctime>

#include <queue>

using namespace std;



const int N = 100010;

int dp[N];

bool vis[N];



int solve(int n) {

	queue<int> q;

	memset(dp, -1, sizeof(dp));

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

		if (dp[i % n] == -1) {

			dp[i % n] = i;

			q.push(i % n);

		    vis[i % n] = true;

		}

	}



	while (!q.empty()) {

		int u = q.front();

		q.pop();

		vis[u] = false;

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

			int x = (10 * u + i) % n;

			if (dp[x] == -1 || dp[x] > dp[u] + i) {

				dp[x] = dp[u] + i;

				if (!vis[x]) {

					vis[x] = true;

					q.push(x);

				}

			}

		}

	}

	return dp[0];

}



int main()

{

	int n;

	scanf("%d", &n);

	

	cout << solve(n) << endl;

	return 0;

}

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

#include<deque>

using namespace std;



int k;

bool vis[200000];

pair<int,int>p;

deque<pair<int,int>>q;



int main()

{

	cin>>k;

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

	while(q.size())

	{

		p=q.front();

		q.pop_front();

		if(vis[p.first])

			continue;

		vis[p.first]=1;

		if(p.first==0)

		{

			cout<<p.second+1;

			return 0;

		}

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

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

	}

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

#include <ext/rope>

using namespace __gnu_cxx;

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))

#define ALL(x) x.begin(),x.end()

#define pii pair<int, int>

#define debug(a) cout << #a": " << a << endl;

#define eularMod(a, b) a < b ? a : a % b + b

inline int lowbit(int x){ return x & -x; }

typedef long long LL;

typedef unsigned long long ULL;

const int N = 1e5 + 10;

const int mod = (int) 1e9 + 7;

const int INF = 0x3f3f3f3f;

const long long LINF = 0x3f3f3f3f3f3f3f3fLL;

const double PI = acos(-1.0);

const double eps = 1e-6;



int k;

int dis[N];

bool inq[N];



int cal(int x) {

    int res = 0;



    for (; x; x /= 10)

        res += x % 10;



    return res;

}



queue<int> Q;



void spfa() {

    mst(dis, 0x3f);



    dis[1] = 1;

    inq[1] = true;



    Q.push(1);



    for (;!Q.empty();) {

        int u = Q.front();

        Q.pop();



        inq[u] = false;



        int v = (u + 1) % k;



        if (dis[v] > dis[u] + 1) {

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



            if (!inq[v])

                Q.push(v);

        }



        v = (u * 10) % k;



        if (dis[v] > dis[u]) {

            dis[v] = dis[u];



            if (!inq[v])

                Q.push(v);

        }

    }

}



int main() {

#ifdef purple_bro

    freopen("in.txt", "r", stdin);

//    freopen("out.txt","w",stdout);

#endif

    scanf("%d", &k);



    spfa();



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

    return 0;

}


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

#include<deque>

using namespace std;



int k;

bool vis[200000];

pair<int,int>p;

deque<pair<int,int>>q;



int main()

{

	cin>>k;

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

	while(q.size())

	{

		p=q.front();

		q.pop_front();

		if(vis[p.first])

			continue;

		vis[p.first]=1;

		if(p.first==0)

		{

			cout<<p.second+1;

			return 0;

		}

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

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

	}

}
// Slower C++ solution:
/*********************

*  Author: xuziyuan  * 

*********************/



#include <bits/stdc++.h>



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

#define repn(i,n) for(int i=1;i<=n;i++)

#define LL long long

#define pii pair <int,int>

#define fi first

#define se second

#define pb push_back

#define mpr make_pair



using namespace std;



const LL MOD=1e9+7;



int n,dist[100010];

deque <int> q;



int main()

{

	cin>>n;

	rep(i,100005) dist[i]=1e9;

	dist[1]=1;

	q.pb(1);

	while(!q.empty())

	{

		int t=q.front();

		q.pop_front();

		if(dist[(t+1)%n]>dist[t]+1)

		{

			dist[(t+1)%n]=dist[t]+1;

			q.pb((t+1)%n);

		}

		if(dist[t*10%n]>dist[t])

		{

			dist[t*10%n]=dist[t];

			q.push_front(t*10%n);

		}

	}

	cout<<dist[0]<<endl;

	return 0;

}

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

#include<deque>

using namespace std;



int k;

bool vis[200000];

pair<int,int>p;

deque<pair<int,int>>q;



int main()

{

	cin>>k;

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

	while(q.size())

	{

		p=q.front();

		q.pop_front();

		if(vis[p.first])

			continue;

		vis[p.first]=1;

		if(p.first==0)

		{

			cout<<p.second+1;

			return 0;

		}

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

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

	}

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

using namespace std;



const int MAX_N=1e5+10;

const int INF=1e9+10;



deque <pair<int,int> > Q;

int K;

vector <pair<int,int> > g[MAX_N];

int dist[MAX_N];



void get_dist(){

	for(int i=0;i<MAX_N;i++) dist[i]=INF;

	dist[1]=1;

	Q.push_back(make_pair(dist[1],1));

	while(Q.size()){

		int val=Q.front().first,x=Q.front().second;

		Q.pop_front();

		if(val>dist[x]) continue;

		for(int i=0;i<g[x].size();i++){

			int cost=g[x][i].first,to=g[x][i].second;

			if(dist[to]>dist[x]+cost){

				dist[to]=dist[x]+cost;

				if(cost==0)

					Q.push_front(make_pair(dist[to],to));

				else

					Q.push_back(make_pair(dist[to],to));

			}

		}

	}

}



int main(){

	scanf("%d",&K);

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

		g[i].push_back(make_pair(0,i*10%K));

		g[i].push_back(make_pair(1,(i+1)%K));

	}

	get_dist();

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

	return 0;

}

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

#include<deque>

using namespace std;



int k;

bool vis[200000];

pair<int,int>p;

deque<pair<int,int>>q;



int main()

{

	cin>>k;

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

	while(q.size())

	{

		p=q.front();

		q.pop_front();

		if(vis[p.first])

			continue;

		vis[p.first]=1;

		if(p.first==0)

		{

			cout<<p.second+1;

			return 0;

		}

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

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

	}

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

}
// 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.426281817510963x):
#include<bits/stdc++.h>



using namespace std; 



const int MAXN = 100000+100, MAXM = 200000+100; 



struct edges{

    int num, to, next; 

}edge[MAXM]; 



int cnt, vis[MAXN], dis[MAXN], head[MAXM], st = 1; 



void addedge(int u, int v, int w){

    edge[++cnt].to = v; 

    edge[cnt].num = w; 

    edge[cnt].next = head[u]; 

    head[u] = cnt; 

}



struct node{

    int dis, num; 

    bool operator <(const node& jbc)const{

        return jbc.dis < dis; 

    }

}; 



void dijkstra(){

    dis[st] = 0; 

    priority_queue<node>heap; 

    heap.push((node){0, st}); 

    while(!heap.empty()){

        node now = heap.top(); 

        heap.pop(); 

        int x = now.num, d = now.dis; 

        if(vis[x])

            continue; 

        vis[x] = 1; 

        if(dis[x] != d)

            continue; 

        for(int i = head[x]; i; i = edge[i].next){

            int y = edge[i].to; 

            if(dis[y] > dis[x] + edge[i].num){

                dis[y] = dis[x] + edge[i].num; 

                if(!vis[y]){

                    heap.push((node){dis[y], y}); 

                }

            }

        }

    }

}



int k; 



int main(){

    cin >> k;

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

    	dis[i] = 0x7fffffff;

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

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

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

    }

    dijkstra();

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

    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: 0.8715560036022586x):
#include<bits/stdc++.h>



using namespace std; 



const int MAXN = 100000+100, MAXM = 200000+100; 



struct edges{

    int num, to, next; 

}edge[MAXM]; 



int cnt, vis[MAXN], dis[MAXN], head[MAXM], st = 1; 



void addedge(int u, int v, int w){

    edge[++cnt].to = v; 

    edge[cnt].num = w; 

    edge[cnt].next = head[u]; 

    head[u] = cnt; 

}



struct node{

    int dis, num; 

    bool operator <(const node& jbc)const{

        return jbc.dis < dis; 

    }

}; 



void dijkstra(){

    dis[st] = 0; 

    priority_queue<node>heap; 

    heap.push((node){0, st}); 

    while(!heap.empty()){

        node now = heap.top(); 

        heap.pop(); 

        int x = now.num, d = now.dis; 

        if(vis[x])

            continue; 

        vis[x] = 1; 

        if(dis[x] != d)

            continue; 

        for(int i = head[x]; i; i = edge[i].next){

            int y = edge[i].to; 

            if(dis[y] > dis[x] + edge[i].num){

                dis[y] = dis[x] + edge[i].num; 

                if(!vis[y]){

                    heap.push((node){dis[y], y}); 

                }

            }

        }

    }

}



int k; 



int main(){

    cin >> k;

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

    	dis[i] = 0x7fffffff;

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

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

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

    }

    dijkstra();

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

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

}
// 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: 4.029737334849371x):
#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

deque< pair<long long,long long> >Que;

int H,T;

bool Visit[100050];

long long K;

int main(){

	scanf("%lld",&K);

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

	while(!Que.empty()){

		pair<long long,long long> Now=Que.front();

		Que.pop_front();

		if(Visit[Now.second]){

			continue;

		}

		Visit[Now.second]=1;

		

		if(Now.second%K==0){

			printf("%lld\n",Now.first);

			break;

		}

		Que.push_front(make_pair(Now.first,(Now.second*10)%K));

		Que.push_back(make_pair(Now.first+1,(Now.second+1)%K));

	}

	return 0;

	//AC!

}
// 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.4614801198436034x):
#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

deque< pair<long long,long long> >Que;

int H,T;

bool Visit[100050];

long long K;

int main(){

	scanf("%lld",&K);

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

	while(!Que.empty()){

		pair<long long,long long> Now=Que.front();

		Que.pop_front();

		if(Visit[Now.second]){

			continue;

		}

		Visit[Now.second]=1;

		

		if(Now.second%K==0){

			printf("%lld\n",Now.first);

			break;

		}

		Que.push_front(make_pair(Now.first,(Now.second*10)%K));

		Que.push_back(make_pair(Now.first+1,(Now.second+1)%K));

	}

	return 0;

	//AC!

}
// 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.22678911057206x):
#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

deque< pair<long long,long long> >Que;

int H,T;

bool Visit[100050];

long long K;

int main(){

	scanf("%lld",&K);

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

	while(!Que.empty()){

		pair<long long,long long> Now=Que.front();

		Que.pop_front();

		if(Visit[Now.second]){

			continue;

		}

		Visit[Now.second]=1;

		

		if(Now.second%K==0){

			printf("%lld\n",Now.first);

			break;

		}

		Que.push_front(make_pair(Now.first,(Now.second*10)%K));

		Que.push_back(make_pair(Now.first+1,(Now.second+1)%K));

	}

	return 0;

	//AC!

}