stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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;  

} 

// 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};

    }

}

//首先我们会发现，任意一个数可以由1开始+1（数字总和+1）或*10（数字总和不变）来得到

//（x9+1是特例，但x9+1明显可以由更优的(x+1)0得到） 

//所以我们可以把数字看成一个个图，起点为x=1，那么按照x到x+1的边权为1 ，x到x*10的边权为0建图 

//那么我们的目标是什么呢？我们发现只要我们凑出一个数x，使x为k的倍数即可，那我们对于一个数字，如果它连向的数字为k的倍数

//我们就让它连向0，最终我们求的就是1到0的最短路

//这是一个01bfs，我们可以使用双端队列来解决 

//时间复杂度O(k) 

// Fastest known solution for this problem:
// Original C++ solution (slower):


#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;

}

// 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};

    }

}

//首先我们会发现，任意一个数可以由1开始+1（数字总和+1）或*10（数字总和不变）来得到

//（x9+1是特例，但x9+1明显可以由更优的(x+1)0得到） 

//所以我们可以把数字看成一个个图，起点为x=1，那么按照x到x+1的边权为1 ，x到x*10的边权为0建图 

//那么我们的目标是什么呢？我们发现只要我们凑出一个数x，使x为k的倍数即可，那我们对于一个数字，如果它连向的数字为k的倍数

//我们就让它连向0，最终我们求的就是1到0的最短路

//这是一个01bfs，我们可以使用双端队列来解决 

//时间复杂度O(k) 

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

}

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

	}

}

// 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<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));

	}

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
/*********************

*  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;

}

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

	}

}

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

}

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

	}

}

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

}


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

}

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

}

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

}

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

}


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

}

// Fastest known solution for this problem:
// Original C++ solution (slower):


#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;

}




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

}



       




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

	

}


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

}

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

}

// 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<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;

}


// 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: