stablegradients/pie-gem5-pairs huggingface dataset:
// 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.705544940926668x):
#include<bits/stdc++.h>

using namespace std;

deque<pair<int,int> > p;

bool flag[100000001];

int l;

void suanfa(){

    while(p.size()) {

        pair<int,int> 

		now=p.front(); 

		p.pop_front();

        if(flag[now.first]) 

		    continue;

        flag[now.first]=true;

        if(!now.first){

            cout<<now.second<<endl;

            return;

        }

        p.push_front(make_pair(now.first*10%l,now.second));

        p.push_back(make_pair((now.first+1)%l,now.second+1));

    }

}

int main() {

    cin>>l;

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

    suanfa();

    return 0;

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

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<deque>

using namespace std;

#define ll long long

#define rg register

#define inf 0x3f3f3f3f

#define MX 100005

#define fi first

#define se second

typedef pair<int,int> PA;

deque<PA> que;

int dis[MX];

int n;

int main(){



    scanf("%d",&n);

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

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

    while(1)

    {

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

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

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

        if(x.fi==0) break;

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

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

    }

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

    return 0;

}

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

using namespace std;

deque<pair<int,int> > p;

bool flag[100000001];

int l;

void suanfa(){

    while(p.size()) {

        pair<int,int> 

		now=p.front(); 

		p.pop_front();

        if(flag[now.first]) 

		    continue;

        flag[now.first]=true;

        if(!now.first){

            cout<<now.second<<endl;

            return;

        }

        p.push_front(make_pair(now.first*10%l,now.second));

        p.push_back(make_pair((now.first+1)%l,now.second+1));

    }

}

int main() {

    cin>>l;

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

    suanfa();

    return 0;

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



using namespace std;



const int maxn=2e5+10;

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

struct Le

{

	int nt,to,dis;

}edge[maxn];



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

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

	edge[num].to=t;

	edge[num].dis=d;

	head[f]=num;

} 



int k;



void spfa(int s) {

	queue<int> q;

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

	dis[s]=1;

	q.push(s);

	vis[s]=1;

	while(!q.empty()) {

		int u=q.front();

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

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

			int v=edge[i].to;

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

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

				if(!vis[v]) {

					q.push(v);

					vis[v]=1;

				}

			}

		}

	}

}



int main() {

	scanf("%d",&k);

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

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

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

	}

	spfa(1);

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

	return 0;

}


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

using namespace std;

deque<pair<int,int> > p;

bool flag[100000001];

int l;

void suanfa(){

    while(p.size()) {

        pair<int,int> 

		now=p.front(); 

		p.pop_front();

        if(flag[now.first]) 

		    continue;

        flag[now.first]=true;

        if(!now.first){

            cout<<now.second<<endl;

            return;

        }

        p.push_front(make_pair(now.first*10%l,now.second));

        p.push_back(make_pair((now.first+1)%l,now.second+1));

    }

}

int main() {

    cin>>l;

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

    suanfa();

    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.692169751714303x):


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

}
// 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: 1.4562052232648361x):


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

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

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>



using namespace std;



#define il inline



constexpr int N=1e5+5;



struct EDGE

{

    int to,nxt,w;

};



int n,cnt;

EDGE e[N*2];

int dis[N],head[N];

bool vis[N];

queue<int>q;



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

{

    e[++cnt].to=y;

    e[cnt].nxt=head[x];

    e[cnt].w=z;

    head[x]=cnt;

}

void SPFA()

{

    for(int i=0;i<n;++i) dis[i]=1e9;

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

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=0;

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

        {

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

            {

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

                if(!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;

            }

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(false);

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

    cin>>n;

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

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

    SPFA();

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

    return 0;

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

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<deque>

using namespace std;

#define ll long long

#define rg register

#define inf 0x3f3f3f3f

#define MX 100005

#define fi first

#define se second

typedef pair<int,int> PA;

deque<PA> que;

int dis[MX];

int n;

int main(){



    scanf("%d",&n);

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

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

    while(1)

    {

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

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

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

        if(x.fi==0) break;

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

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

    }

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

    return 0;

}

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

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>



using namespace std;



#define il inline



constexpr int N=1e5+5;



struct EDGE

{

    int to,nxt,w;

};



int n,cnt;

EDGE e[N*2];

int dis[N],head[N];

bool vis[N];

queue<int>q;



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

{

    e[++cnt].to=y;

    e[cnt].nxt=head[x];

    e[cnt].w=z;

    head[x]=cnt;

}

void SPFA()

{

    for(int i=0;i<n;++i) dis[i]=1e9;

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

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=0;

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

        {

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

            {

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

                if(!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;

            }

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(false);

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

    cin>>n;

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

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

    SPFA();

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

    return 0;

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



using namespace std;



const int maxn=2e5+10;

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

struct Le

{

	int nt,to,dis;

}edge[maxn];



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

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

	edge[num].to=t;

	edge[num].dis=d;

	head[f]=num;

} 



int k;



void spfa(int s) {

	queue<int> q;

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

	dis[s]=1;

	q.push(s);

	vis[s]=1;

	while(!q.empty()) {

		int u=q.front();

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

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

			int v=edge[i].to;

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

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

				if(!vis[v]) {

					q.push(v);

					vis[v]=1;

				}

			}

		}

	}

}



int main() {

	scanf("%d",&k);

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

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

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

	}

	spfa(1);

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

	return 0;

}


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

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>



using namespace std;



#define il inline



constexpr int N=1e5+5;



struct EDGE

{

    int to,nxt,w;

};



int n,cnt;

EDGE e[N*2];

int dis[N],head[N];

bool vis[N];

queue<int>q;



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

{

    e[++cnt].to=y;

    e[cnt].nxt=head[x];

    e[cnt].w=z;

    head[x]=cnt;

}

void SPFA()

{

    for(int i=0;i<n;++i) dis[i]=1e9;

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

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=0;

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

        {

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

            {

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

                if(!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;

            }

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(false);

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

    cin>>n;

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

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

    SPFA();

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

    return 0;

}
// Slower C++ solution:


#include<cstdio>

#include<algorithm>

#include<queue>

#include<cmath>

#include<iostream>

#include<cstring>

#define ll long long

#define maxn 100005

			 

#define p 1000000007

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

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

using namespace std;

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

//_____________________________________________________________________________________________________

deque<int>q;

int vis[maxn],dis[maxn];

int main()

{

	int k = read();

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

	dis[1] = 1;

	q.push_back(1);

	while(!q.empty() )

	{

		int x = q.front() ; 

		q.pop_front() ;

		if(vis[x])

			continue;

		vis[x] = 1;

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

		{

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

			q.push_front(x*10%k);

		}

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

		{

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

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

		}

	}

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

    return 0;

}




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

#include<iostream>

#include<cstring>

#include<queue>

#include<algorithm>



using namespace std;



#define il inline



constexpr int N=1e5+5;



struct EDGE

{

    int to,nxt,w;

};



int n,cnt;

EDGE e[N*2];

int dis[N],head[N];

bool vis[N];

queue<int>q;



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

{

    e[++cnt].to=y;

    e[cnt].nxt=head[x];

    e[cnt].w=z;

    head[x]=cnt;

}

void SPFA()

{

    for(int i=0;i<n;++i) dis[i]=1e9;

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

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        vis[x]=0;

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

        {

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

            {

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

                if(!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;

            }

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(false);

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

    cin>>n;

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

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

    SPFA();

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

using namespace std;

typedef long long LL;

bool vis[100005];

LL k;

deque<pair<LL, LL> > dq;

int main()

{

	cin >> k;

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

	while(!dq.empty())

	{

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

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

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

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

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

	}

	return 0;

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

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

using namespace std;

typedef long long LL;

bool vis[100005];

LL k;

deque<pair<LL, LL> > dq;

int main()

{

	cin >> k;

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

	while(!dq.empty())

	{

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

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

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

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

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

	}

	return 0;

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

using namespace std;

typedef long long LL;

bool vis[100005];

LL k;

deque<pair<LL, LL> > dq;

int main()

{

	cin >> k;

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

	while(!dq.empty())

	{

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

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

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

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

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

	}

	return 0;

}