stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define int long long

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

#define ini(x,y) memset(x,y,sizeof(x))

#define cauto const auto &

#define cint const int &

#define F(x, y, z) for (int x = y; x <= z; x++)

#define D(x, y, z) for (int x = y; x >= z; x--)

using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3f;

const int MAXN = static_cast<int>(1e5 + 25);

inline int read()

{

  int x = 0, y = 1, c = getchar();

  while (c > '9' || c < '0')

  {

    if (c == '-')

    {

      y = -1;

    }

    c = getchar();

  }

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

  {

    x = x * 10 + c - '0';

    c = getchar();

  }

  return x * y;

}

/*

 * 用最短的时间取得胜利！！！！

*/

struct road{

    int to,v;

    road(int to=0,int v=0):to(to),v(v){}

};



static vector<road> edge[MAXN];

struct heapnode{

    int to,val;

    heapnode(int T=0,int V=0):to(T),val(V){}

    bool operator<(const heapnode r)const{

        return val>r.val;

    }

};

static priority_queue<heapnode> q;

static int d[MAXN];

void dijkstra(){

    ini(d,0x3f);

    d[0]=0;

    q.push(heapnode(0,0));

    while(!q.empty()){

        int pos=q.top().to;

        q.pop();

        for(auto to:edge[pos]){



            if(d[pos]+to.v<d[to.to]){

                d[to.to]=d[pos]+to.v;//cout<<pos<<" "<<to.to<<" "<<d[to.to]<<endl;

                q.push(heapnode(to.to,d[to.to]));

            }

        }

    }

}

signed main(){

    int k=read();

    F(i,1,k-1){

        int now=i;

        F(j,1,9){

            edge[(i+j)%k].push_back(road(i,j));

            now*=10;

            edge[now%k].push_back(road(i,0));

        }

    }

    dijkstra();

//    int minn=INF;

    printf("%lld",d[1]+1);

    return 0;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int N=1e6;

bool vis[N];

deque <pair<int,int> > q;

int k;

void bfs()

{

	while(!q.empty())

	{

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

		q.pop_front();

		if(vis[t.first]) continue;

		vis[t.first]=true;

		if(!t.first)

		{

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

			exit(0);

		}

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

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

	}

}

int main()

{

	scanf("%d",&k);

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

	bfs();

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int read()

{

    int d = 0, w = 1;

    char ch = getchar();

    while (ch != '-' && (ch < '0' || ch > '9'))

        ch = getchar();

    if (ch == '-')

        w = -1, ch = getchar();

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

        d = d * 10 + ch - '0', ch = getchar();

    return d * w;

}

void write_(int x)

{

    if (x < 0)

        x = -x, putchar('-');

    if (x > 9)

        write_(x / 10);

    putchar(x % 10 + '0');

}

void writeln(int x)

{

    write_(x);

    putchar('\n');

}

void writesp(int x)

{

    write_(x);

    putchar(' ');

}

int vis[111000];

int main()

{

#ifdef __clang__

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

    freopen("data.out", "w", stdout);

#endif

    using P = pair<int, int>;

    int K = read();

    deque<P> de;

    de.push_back({1, 1});

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

    while(1)

    {

        P p = de.back();

        de.pop_back();

        if(p.second >= vis[p.first])

            continue;

        vis[p.first] = p.second;

        if(p.first == 0)

        {

            writeln(p.second);

            return 0;

        }

        de.push_back({p.first * 10 % K, p.second});

        de.push_front({(p.first + 1) % K, p.second + 1});

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int N=1e6;

bool vis[N];

deque <pair<int,int> > q;

int k;

void bfs()

{

	while(!q.empty())

	{

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

		q.pop_front();

		if(vis[t.first]) continue;

		vis[t.first]=true;

		if(!t.first)

		{

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

			exit(0);

		}

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

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

	}

}

int main()

{

	scanf("%d",&k);

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

	bfs();

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;



const int N=200200,inf=0x3f3f3f3f;



int k;



struct edge

{

	int from,to,w,nextt;

}g[N];

int head[N],cnt=0;

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

{

	cnt++;g[cnt].nextt=head[u];head[u]=cnt;g[cnt].to=v;g[cnt].from=u;g[cnt].w=w;

}



int dist[N],inq[N];queue<int> q;

void spfa()

{

	memset(dist,0x3f,sizeof dist);

	dist[1]=0;inq[1]=1;q.push(1);

	while (!q.empty())

	{

		int u=q.front();inq[u]=0;q.pop();

		for (int i=head[u];i;i=g[i].nextt)

		{

			int v=g[i].to,w=g[i].w;

			if (dist[v]>dist[u]+w)

			{

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

				if (!inq[v]){inq[v]=1;q.push(v);}

			}

		}

			

	}

}





int main()

{

	cin>>k;

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

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

	spfa();

	cout<<dist[0]+1;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int N=1e6;

bool vis[N];

deque <pair<int,int> > q;

int k;

void bfs()

{

	while(!q.empty())

	{

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

		q.pop_front();

		if(vis[t.first]) continue;

		vis[t.first]=true;

		if(!t.first)

		{

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

			exit(0);

		}

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

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

	}

}

int main()

{

	scanf("%d",&k);

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

	bfs();

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std ;

#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )

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

#define re register

int gi() {

	char cc = getchar() ; int cn = 0, flus = 1 ;

	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }

	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;

	return cn * flus ;

}

const int M = 1e5 + 5 ; 

struct E {

	int to, next, w ;

} e[M * 20] ; 

int n, m, cnt, head[M], dis[M], vis[M] ; 

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

	e[++ cnt] = (E){ y, head[x], z }, head[x] = cnt ; 

}

queue<int> q ;

void spfa() {

	memset( dis, 63, sizeof(dis) ) ;

	rep( i, 1, 9 ) {

		dis[i % n] = min( dis[i % n], i ) ;

		if( !vis[i % n] ) q.push(i % n), vis[i % n] = 1 ;

	}

	while( !q.empty() ) {

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

		Next( i, u ) {

			int v = e[i].to ; 

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

				dis[v] = dis[u] + e[i].w ;

				if( !vis[v] ) q.push(v), vis[v] = 1 ;

			}

		}

	}

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

}

signed main()

{

	n = gi() ; 

	rep( i, 0, n - 1 ) rep( j, 0, 9 )

	add( i, ( i * 10 + j ) % n, j ) ;

	spfa() ; 

	return 0 ;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int N=1e6;

bool vis[N];

deque <pair<int,int> > q;

int k;

void bfs()

{

	while(!q.empty())

	{

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

		q.pop_front();

		if(vis[t.first]) continue;

		vis[t.first]=true;

		if(!t.first)

		{

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

			exit(0);

		}

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

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

	}

}

int main()

{

	scanf("%d",&k);

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

	bfs();

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define fi			first

#define se			second

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

#define fd(i,a,b)	for(int i=a;i>=b;i--)

#define put(x)		putchar(x)

#define eoln        put('\n')

#define space		put(' ')

inline int read(){

	int x=0,neg=1;char c=getchar();

	while(!isdigit(c)){

		if(c=='-')	neg=-1;

		c=getchar();

	}

	while(isdigit(c))	x=x*10+c-'0',c=getchar();

	return x*neg;

}

inline void print(int x){

	if(x<0){

		putchar('-');

		print(abs(x));

		return;

	}

	if(x<=9)	putchar(x+'0');

	else{

		print(x/10);

		putchar(x%10+'0');

	}

}

int n=read();

struct edge{

	int u,v,w;

};

vector<edge> g[100005];

int dist[100005];

inline void dijkstra(){

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

	memset(dist,63,sizeof(dist));

	dist[1]=1;

	pq.push({1,1});

	while(!pq.empty()){

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

		pq.pop();

		int s=p.first,x=p.second;

		if(s>dist[x])	continue;

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

			int y=g[x][i].v,z=g[x][i].w;

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

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

				pq.push({dist[y],y});

			}

		}

	}

}

int main(){

	fz(i,0,n-1){

		if(i!=0)	g[i].push_back({i,i*10%n,0});

		g[i].push_back({i,(i+1)%n,1});

	}

	dijkstra();

	print(dist[0]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int N=1e6;

bool vis[N];

deque <pair<int,int> > q;

int k;

void bfs()

{

	while(!q.empty())

	{

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

		q.pop_front();

		if(vis[t.first]) continue;

		vis[t.first]=true;

		if(!t.first)

		{

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

			exit(0);

		}

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

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

	}

}

int main()

{

	scanf("%d",&k);

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

	bfs();

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<queue>

using namespace std;

int k,cnt,inf=0x3f3f3f3f,inqueue[100001],head[100001],dis[100001];

struct bian{

	int to;

	int cost;

    int next;

}edge[200001];

void addedge(int u,int v,int cost)

{

	edge[++cnt].to=v;

	edge[cnt].cost=cost;

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

	head[u]=cnt;

}

int main()

{

	cin>>k;

	for(int i=0;i<=100000;i++)head[i]=-1,dis[i]=inf;

	for(int i=0;i<=k-1;i++)addedge(i,(i+1)%k,1);

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

	queue <int> q;

	q.push(1);dis[1]=1;inqueue[1]=1;

	while(!q.empty())

	{

		int from=q.front();

		q.pop();

		inqueue[from]=0;

		for(int i=head[from];i!=-1;i=edge[i].next)

		{

			int to=edge[i].to,cost=edge[i].cost;

			if(dis[from]+cost<dis[to])

			{

				dis[to]=dis[from]+cost;

				if(inqueue[to]==0)

				{

					inqueue[to]=1;

					q.push(to);

				}

		    }

		}

	}

	cout<<dis[0]<<endl;

	return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct node{

	int pre, to, val;

}edge[200010];

int head[100010], tot;

int k;

void add(int u, int v, int l) {

	edge[++tot] = node{head[u], v, l};

	head[u] = tot;

}

int dis[100010], vis[100010];

queue<int> q;

void spfa() {

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

	dis[1] = 1;

	vis[1] = 1;

	q.push(1);

	while (!q.empty()) {

		int x = q.front(); q.pop();

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

			int y = edge[i].to;

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

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

				if (!vis[y]) {

					vis[y] = 1;

					q.push(y);

				}

			}

		}

		vis[x] = 0;

	}

}

int main() {

	cin >> k;

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

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

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

	}

	spfa();

	cout << dis[0];

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <deque>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	deque<int> q;

	q.push_back(1);

	while (q.front()) {

		int u = q.front();

		q.pop_front();

		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;

			i ? q.push_back(v) : q.push_front(v);

		}

	}

	cout << *d << endl;

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <deque>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	deque<int> q;

	q.push_back(1);

	while (q.front()) {

		int u = q.front();

		q.pop_front();

		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;

			i ? q.push_back(v) : q.push_front(v);

		}

	}

	cout << *d << endl;

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//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;

}

// Optimized solution to the same problem (faster):
#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};

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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};

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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};

    }

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
//#include<bits/stdc++.h>

#include<iostream>

#include<cstring>

#include<deque>

#include<string>

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

#define lowbit(x) (x&(-x))

#define lson        (rt<<1)

#define rson        (rt<<1|1)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

const int maxn = 2e5+50;

const int inf = 0x3f3f3f3f;

const ll INF = 0x3f3f3f3f3f3f3f3f;

const int mod = 1e9 + 7;

int dis[maxn];

bool vis[maxn];

deque<int>qu;



int main() {

#ifdef local

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

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

#endif

//freopen("G.IN","r",stdin);

    ios::sync_with_stdio(false);

    cin.tie(0);cout.tie(0);

    int k;cin>>k;

    mst(dis,0x3f);

    qu.push_back(1);dis[1]=1;

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

        int a=qu.front();qu.pop_front();

        if(vis[a])continue;

        int g=(a*10)%k;

        if(!vis[g] and dis[a]<dis[g]){

            dis[g]=dis[a];

            qu.push_front(g);

        }

        g=(a+1)%k;

        if(!vis[g] and dis[a]+1<dis[g]){

            dis[g]=dis[a]+1;

            qu.push_back(g);

        }

    }

    cout<<dis[0];

    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

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

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;



int k;

int num[100010],out = 100010; 

bool v[100010],l,l2;



void dfs()

{

	queue < int > q;

	q.push(0);

	v[0] = 0;

	while(!q.empty())

	{

		int now = q.front();

		if(now == 0)

		{

			if(l2 == 0) l2 = 1;

			else

			{

				out = min(out,num[now]);

				l = 1;

			}

		}

		if((num[(now + 1) % k] > num[now] + 1 || num[(now + 1) % k] == -1) && l == 0)

		{

			num[(now + 1) % k] = num[now] + 1;

			if(v[(now + 1) % k] == 0)

			q.push((now + 1) % k);

			v[(now + 1) % k] = 1;

		}

		if((num[now * 10 % k] > num[now] || num[now * 10 % k] == -1) && now * 10 % k != now && l == 0)

		{

			num[now * 10 % k] = num[now];

			if(v[now * 10 % k] == 0)

			q.push(now * 10 % k);

			v[now * 10 % k] = 1;

		}

		v[now] = 0;

		q.pop();

		l = 0;

		if(now == 0)

		num[now] = -1;

	}

}



int main()

{

	cin>>k;

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

	num[i] = -1;

	

	dfs();

	

	cout<<out;

	

	return 0;

}


// Fastest known solution for this problem: