stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <iostream>

#include <set>



using namespace std;



const int L = 10;

struct dist {

	int s, N[L];

	dist() :s(100) {

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

			N[i] = !i;

	}

	dist(const dist &p, int i) :s(p.s + i) {

		//if (*p.N < 0) {

		//	*N = -1;

		//	return;

		//}

		//int k = i;

		//for (int j = 0; j < L; j++) {

		//	N[j] = i ? p.N[j] + k : p.N[j] * 10 + k;

		//	k = N[j] / 100000000;

		//	N[j] %= 100000000;

		//}

		//if (k) *N = -1;

	}

	bool operator<(const dist &d) const {

		if (s != d.s)

			return s < d.s;

		//if (*N < 0)

		//	return false;

		//else if (*d.N < 0)

		//	return true;

		//for (int i = L; i--;)

		//	if (N[i] != d.N[i])

		//		return N[i] < d.N[i];

		return false;

	}

} d[114514];



struct vert {

	int r;

	vert(int r) :r(r) {}

	bool operator<(const vert &v) const {

		if (d[r] < d[v.r])

			return true;

		if (d[v.r] < d[r])

			return false;

		return r < v.r;

	}

};



int main()

{

	int k;

	cin >> k;

	d[1].s = 1;

	set<vert> q;

	q.insert(1);

	while (!q.empty()) {

		int u = q.begin()->r;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			dist l(d[u], i);

			if (!(l < d[v]))

				continue;

			auto it = q.find(v);

			if (it != q.end())

				q.erase(it);

			d[v] = l;

			q.insert(v);

		}

	}

	cout << d->s << endl;

	//if (*d->N < 0) {

	//	cout << "inf" << endl;

	//	return 0;

	//}

	//for (int i = L; i--;) {

	//	if (!k) {

	//		cout.fill('0');

	//		cout.width(8);

	//		cout << right << d->N[i];

	//	}

	//	else if (d->N[i]) {

	//		k = 0;

	//		cout << d->N[i];

	//	}

	//}

	//cout << endl;

	return 0;

}


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

#include <set>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	set<pair<int, int>> q;

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

	while (q.begin()->second) {

		int u = q.begin()->second;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			auto it = q.find(make_pair(d[v], v));

			if (it != q.end())

				q.erase(it);

			d[v] = d[u] + i;

			q.insert(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

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



using namespace std;



bool d[114514][46];

int M;

void f(int r, int s, int m)

{

	if (s > 45 || d[r][s])

		return;

	d[r][s] = true;

	if (!r && s && (!M || s < M))

		M = s;

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

		f((r * 10 + i) % m, s + i, m);

}



int main()

{

	int k;

	cin >> k;

	f(0, 0, k);

	cout << M << endl;

	return 0;

}


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

#include <queue>

#include <functional>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

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

	while (q.top().second) {

		int u = q.top().second;

		q.pop();

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			d[v] = d[u] + i;

			q.push(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

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

#include <set>



using namespace std;



const int L = 10;

struct dist {

	int s, N[L];

	dist() :s(100) {

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

			N[i] = !i;

	}

	dist(const dist &p, int i) :s(p.s + i) {

		//if (*p.N < 0) {

		//	*N = -1;

		//	return;

		//}

		//int k = i;

		//for (int j = 0; j < L; j++) {

		//	N[j] = i ? p.N[j] + k : p.N[j] * 10 + k;

		//	k = N[j] / 100000000;

		//	N[j] %= 100000000;

		//}

		//if (k) *N = -1;

	}

	bool operator<(const dist &d) const {

		if (s != d.s)

			return s < d.s;

		//if (*N < 0)

		//	return false;

		//else if (*d.N < 0)

		//	return true;

		//for (int i = L; i--;)

		//	if (N[i] != d.N[i])

		//		return N[i] < d.N[i];

		return false;

	}

} d[114514];



struct vert {

	int r;

	vert(int r) :r(r) {}

	bool operator<(const vert &v) const {

		if (d[r] < d[v.r])

			return true;

		if (d[v.r] < d[r])

			return false;

		return r < v.r;

	}

};



int main()

{

	int k;

	cin >> k;

	d[1].s = 1;

	set<vert> q;

	q.insert(1);

	while (!q.empty()) {

		int u = q.begin()->r;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			dist l(d[u], i);

			if (!(l < d[v]))

				continue;

			auto it = q.find(v);

			if (it != q.end())

				q.erase(it);

			d[v] = l;

			q.insert(v);

		}

	}

	cout << d->s << endl;

	//if (*d->N < 0) {

	//	cout << "inf" << endl;

	//	return 0;

	//}

	//for (int i = L; i--;) {

	//	if (!k) {

	//		cout.fill('0');

	//		cout.width(8);

	//		cout << right << d->N[i];

	//	}

	//	else if (d->N[i]) {

	//		k = 0;

	//		cout << d->N[i];

	//	}

	//}

	//cout << endl;

	return 0;

}


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

#include <queue>

#include <functional>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

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

	while (q.top().second) {

		int u = q.top().second;

		q.pop();

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			d[v] = d[u] + i;

			q.push(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

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

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

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



using namespace std;

typedef long long ll;



const int MAXN = 1e5+100;

const int INF = 1e9;

int dist[MAXN];



int main(){

  int k;

  cin >> k;

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

  dist[k] = 0;  

  

  deque<int> dq;

  dq.push_front(k);

  while(!dq.empty()){

    int u = dq.front();

    dq.pop_front();

    int nxt0 = u == k ? k : (10 * u) % k;

    int nxt1 = (u + 1) % k;

    if(dist[u] < dist[nxt0]){

      dist[nxt0] = dist[u];

      dq.push_front(nxt0);

    }

    if(dist[u] + 1 < dist[nxt1]){

      dist[nxt1] = dist[u] + 1;

      dq.push_back(nxt1);

    }

  }

  cout<<dist[0]<<endl;

  return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

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

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

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

using namespace std;

typedef pair<int,int> p;

	  int n;

	  int v[1<<17];

	  p m;

    deque<p> q;

#define M(a,b) make_pair(a,b)

#define N first 

#define S second 

int main()

{

  cin>>n;

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

  while (1)

    {

      m=q.front();

      q.pop_front();

			if (!m.N) break;

			if (v[m.N]) continue;

			v[m.N]=1;

			q.push_front(M(m.N*10%n,m.S));

			q.push_back(M((m.N+1)%n,m.S+1));

    }

	cout<<m.S;

	return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

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

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

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

using namespace std;

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

#define ll long long

int k,a[100001],vis[100001];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

int c[100001];

int main(){

	scanf("%d",&k);

	memset(a,0x3f,sizeof a);

	a[1]=1; pq.push(make_pair(1,1));

	while(!pq.empty()){

		pair<int,int> P=pq.top(); pq.pop();

		int u=P.second, d=P.first;

		if(vis[u]) continue;

		int v=(u+1)%k;

		if(a[v]>d+1) a[v]=d+1, pq.push(make_pair(a[v],v));

		for(int i=u;;i=i*10%k){

			if(c[i]||vis[i]) break;

			if(a[i]>d) a[i]=d, pq.push(make_pair(a[i],i));

			c[i]=1;

		}

		for(int i=u;;i=i*10%k){

			if(!c[i]) break;

			c[i]=0;

		}

		vis[u]=1;

	} printf("%d",a[0]);

	return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

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

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

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

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

int k,cnt=0,h[100005],dis[100005];

struct Edge{

	int to,next,w;

}e[400005];

queue<int> q;

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

	e[++cnt].to=v;

	e[cnt].next=h[u];

	e[cnt].w=w;

	h[u]=cnt;

}

inline void init(){

	scanf("%d",&k);

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

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

		add(i,i+1,1);

	}

	add(k-1,(k-1)*10%k,0);

	add(k-1,0,1);

	memset(dis,127/3,sizeof(dis));

	dis[1]=0;

}

int main(){

	init();

	q.push(1);

	while(!q.empty()){

		int x=q.front();

		q.pop();

		for(int i=h[x];i;i=e[i].next)

			if(dis[e[i].to]>dis[x]+e[i].w){

				dis[e[i].to]=dis[x]+e[i].w;

				q.push(e[i].to);

			}

	}

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

	return 0;

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

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

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

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

using namespace std;

struct P{int a,b;}q[200005];

int k,l=100000,r=100000;

bool book[100005];

int main(){

    scanf("%d", &k);

    q[l]={1,1};

    while(l<=r){

    	P x=q[l++];

        if(book[x.a]) continue; book[x.a]=1;

        if(x.a==0){printf("%d\n",x.b);break;}

        q[--l]={x.a*10%k,x.b};

        q[++r]={(x.a+1)%k,x.b+1};

    }

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

using namespace std;

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

#define ll long long

int k,a[100001],vis[100001];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

int c[100001];

int main(){

	scanf("%d",&k);

	memset(a,0x3f,sizeof a);

	a[1]=1; pq.push(make_pair(1,1));

	while(!pq.empty()){

		pair<int,int> P=pq.top(); pq.pop();

		int u=P.second, d=P.first;

		if(vis[u]) continue;

		int v=(u+1)%k;

		if(a[v]>d+1) a[v]=d+1, pq.push(make_pair(a[v],v));

		for(int i=u;;i=i*10%k){

			if(c[i]||vis[i]) break;

			if(a[i]>d) a[i]=d, pq.push(make_pair(a[i],i));

			c[i]=1;

		}

		for(int i=u;;i=i*10%k){

			if(!c[i]) break;

			c[i]=0;

		}

		vis[u]=1;

	} printf("%d",a[0]);

	return 0;

}

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

using namespace std;

struct P{int a,b;}q[200005];

int k,l=100000,r=100000;

bool book[100005];

int main(){

    scanf("%d", &k);

    q[l]={1,1};

    while(l<=r){

    	P x=q[l++];

        if(book[x.a]) continue; book[x.a]=1;

        if(x.a==0){printf("%d\n",x.b);break;}

        q[--l]={x.a*10%k,x.b};

        q[++r]={(x.a+1)%k,x.b+1};

    }

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

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

int k,cnt=0,h[100005],dis[100005];

struct Edge{

	int to,next,w;

}e[400005];

queue<int> q;

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

	e[++cnt].to=v;

	e[cnt].next=h[u];

	e[cnt].w=w;

	h[u]=cnt;

}

inline void init(){

	scanf("%d",&k);

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

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

		add(i,i+1,1);

	}

	add(k-1,(k-1)*10%k,0);

	add(k-1,0,1);

	memset(dis,127/3,sizeof(dis));

	dis[1]=0;

}

int main(){

	init();

	q.push(1);

	while(!q.empty()){

		int x=q.front();

		q.pop();

		for(int i=h[x];i;i=e[i].next)

			if(dis[e[i].to]>dis[x]+e[i].w){

				dis[e[i].to]=dis[x]+e[i].w;

				q.push(e[i].to);

			}

	}

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

	return 0;

}

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

using namespace std;

struct P{int a,b;}q[200005];

int k,l=100000,r=100000;

bool book[100005];

int main(){

    scanf("%d", &k);

    q[l]={1,1};

    while(l<=r){

    	P x=q[l++];

        if(book[x.a]) continue; book[x.a]=1;

        if(x.a==0){printf("%d\n",x.b);break;}

        q[--l]={x.a*10%k,x.b};

        q[++r]={(x.a+1)%k,x.b+1};

    }

}
// Slower C++ solution:
//Dile a la jardinera que traigo flores

#include <bits/stdc++.h>



#define fst first

#define snd second

#define mp make_pair

#define pb push_back

#define sz(x) (int)x.size()

#define trace(x) cout << #x << " = " << x << endl

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

#define iFR(i,a) for(int i = int(a-1); i >= int(0); i--)

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)



using namespace std;



typedef long long ll;

typedef pair<int,int> ii;



const int N=1e5+5;

vector<ii>gfo[N];int d[N];



inline void build(int n){

	FOR(i,1,n)FOR(j,0,10)

		gfo[i].pb(mp((10*i+j)%n,j));

}



inline int dijkstra(int n){

	priority_queue<ii,vector<ii>,greater<ii> >pq;

	FOR(i,0,N)d[i]=INT_MAX;

	FOR(i,1,10)if(d[i]>i){

		d[i]=i;pq.push(mp(i,i%n));

	}

	while(!pq.empty()){

		ii ini=pq.top();pq.pop();

		int dist=ini.fst;

		int u=ini.snd;

		if(dist>d[u])continue;

		for(ii v:gfo[u])if(d[u]+v.snd<d[v.fst]){

			d[v.fst]=d[u]+v.snd;

			pq.push(mp(d[v.fst],v.fst));

		}

	}

	return d[0];

}



int main(){

	int n;scanf("%d",&n);

	build(n);

	int res=dijkstra(n);

	cout<<res<<endl;

	return 0;

}

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

#define ll long long

using namespace std;

const int N = 1000001;

struct node{

    int v,nxt,cost;

}edge[N];

int head[N],k,tot;

int q[N],l,r,u,v;

int dist[N];

void addEdge(int u,int v,int val) {

    edge[++tot].v=v;

    edge[tot].cost=val;

    edge[tot].nxt=head[u];

    head[u]=tot;

}

int main() {

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

    scanf("%d",&k);

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

        addEdge(i,i+1==k?0:i+1,1);

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

        dist[i]=N;

    }

    dist[1]=0;

    l=-1;

    r=0;

    q[0]=1;

    while (l<r) {

        u = q[++l];

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

            v=edge[i].v;

            if (dist[u]+edge[i].cost<dist[v]) {

                dist[v]=dist[u]+edge[i].cost;

                q[++r]=v;

            }

        }

    }

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

    return 0;

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

using namespace std;

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

#define ll long long

int k,a[100001],vis[100001];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

int c[100001];

int main(){

	scanf("%d",&k);

	memset(a,0x3f,sizeof a);

	a[1]=1; pq.push(make_pair(1,1));

	while(!pq.empty()){

		pair<int,int> P=pq.top(); pq.pop();

		int u=P.second, d=P.first;

		if(vis[u]) continue;

		int v=(u+1)%k;

		if(a[v]>d+1) a[v]=d+1, pq.push(make_pair(a[v],v));

		for(int i=u;;i=i*10%k){

			if(c[i]||vis[i]) break;

			if(a[i]>d) a[i]=d, pq.push(make_pair(a[i],i));

			c[i]=1;

		}

		for(int i=u;;i=i*10%k){

			if(!c[i]) break;

			c[i]=0;

		}

		vis[u]=1;

	} printf("%d",a[0]);

	return 0;

}

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

#define ll long long

using namespace std;

const int N = 1000001;

struct node{

    int v,nxt,cost;

}edge[N];

int head[N],k,tot;

int q[N],l,r,u,v;

int dist[N];

void addEdge(int u,int v,int val) {

    edge[++tot].v=v;

    edge[tot].cost=val;

    edge[tot].nxt=head[u];

    head[u]=tot;

}

int main() {

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

    scanf("%d",&k);

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

        addEdge(i,i+1==k?0:i+1,1);

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

        dist[i]=N;

    }

    dist[1]=0;

    l=-1;

    r=0;

    q[0]=1;

    while (l<r) {

        u = q[++l];

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

            v=edge[i].v;

            if (dist[u]+edge[i].cost<dist[v]) {

                dist[v]=dist[u]+edge[i].cost;

                q[++r]=v;

            }

        }

    }

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

    return 0;

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

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

int k,cnt=0,h[100005],dis[100005];

struct Edge{

	int to,next,w;

}e[400005];

queue<int> q;

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

	e[++cnt].to=v;

	e[cnt].next=h[u];

	e[cnt].w=w;

	h[u]=cnt;

}

inline void init(){

	scanf("%d",&k);

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

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

		add(i,i+1,1);

	}

	add(k-1,(k-1)*10%k,0);

	add(k-1,0,1);

	memset(dis,127/3,sizeof(dis));

	dis[1]=0;

}

int main(){

	init();

	q.push(1);

	while(!q.empty()){

		int x=q.front();

		q.pop();

		for(int i=h[x];i;i=e[i].next)

			if(dis[e[i].to]>dis[x]+e[i].w){

				dis[e[i].to]=dis[x]+e[i].w;

				q.push(e[i].to);

			}

	}

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

	return 0;

}

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

#define ll long long

using namespace std;

const int N = 1000001;

struct node{

    int v,nxt,cost;

}edge[N];

int head[N],k,tot;

int q[N],l,r,u,v;

int dist[N];

void addEdge(int u,int v,int val) {

    edge[++tot].v=v;

    edge[tot].cost=val;

    edge[tot].nxt=head[u];

    head[u]=tot;

}

int main() {

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

    scanf("%d",&k);

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

        addEdge(i,i+1==k?0:i+1,1);

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

        dist[i]=N;

    }

    dist[1]=0;

    l=-1;

    r=0;

    q[0]=1;

    while (l<r) {

        u = q[++l];

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

            v=edge[i].v;

            if (dist[u]+edge[i].cost<dist[v]) {

                dist[v]=dist[u]+edge[i].cost;

                q[++r]=v;

            }

        }

    }

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

    return 0;

}