stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

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

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

#define pq priority_queue

#define P pair<ll,ll>

#define P2 pair<int,P>

#define P3 pair<int,P2>

typedef long long ll; typedef long double ld;

using namespace std;

const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};

const ll LINF=1e18;

const ld PI=abs(acos(-1));

int k;

vector<P> g[100010];



ll dijkstra(int s, int t){

	ll min_cost[100010]={};

	pq<P, vector<P>, greater<P>> que;

	REP(i,0,k) min_cost[i]=INF;

	que.emplace(0,s);

	min_cost[s]=0;

	while(!que.empty()){

		auto p=que.top(); que.pop();

		if(p.first>min_cost[p.second]) continue;



		for(auto e:g[p.second]){

			if(p.first+e.second>=min_cost[e.first]) continue;

			min_cost[e.first]=p.first+e.second;

			que.emplace(min_cost[e.first], e.first);

		}

	}



	return min_cost[t];

}



int main(){

	cin >> k;

	REP(i,0,k) g[i].push_back(P((i*10)%k,0)),g[i].push_back(P((i+1)%k,1));

	

	cout << dijkstra(1,0)+1 << endl;

	return 0;

}


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

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

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

#define pq priority_queue

#define P pair<int,int>

#define P2 pair<int,P>

#define P3 pair<int,P2>

typedef long long ll; typedef long double ld;

using namespace std;

const int INF=1e9, MOD=1e9+7, around[]={0,1,1,-1,-1,0,-1,1,0,0};

const ll LINF=1e18;

const ld PI=abs(acos(-1));



vector<P> g[100010];

int n;



int solve(){

	int min_cost[100010]; REP(i,0,n) min_cost[i] = INF;

	deque<P> qu; qu.push_front({1,1}); min_cost[1] = 0;

	

	while(!qu.empty()){

		auto p = qu.front(); qu.pop_front();

		

		for(auto e:g[p.second]){

			if(p.first + e.second >= min_cost[e.first]) continue;

			min_cost[e.first] = p.first + e.second;

			

			if(e.second) qu.push_back({min_cost[e.first], e.first});

			else qu.push_front({min_cost[e.first], e.first});

		}

	}

	

	return min_cost[0];

}



int main(){

	cin >> n;

	

	REP(i,0,n){

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

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

	}

	

	cout << solve() << endl;

	return 0;

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

#define maxn 100005

#define ll long long

using namespace std;

int k;

int dis[maxn];

struct edge

{

	int v,w;

	edge(int v=0,int w=0):v(v),w(w){}

};

vector<edge>adj[maxn];

bool vis[maxn];

void bfs()

{

	queue<int>q;

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

	dis[1]=1;vis[1]=true;

	q.push(1);

	int u,v,w;

	while(!q.empty())

	{

		u=q.front();

		q.pop();

		vis[u]=0;

		int sz=adj[u].size();

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

		{

			v=adj[u][i].v;

			w=adj[u][i].w;

			if(dis[u]+w<dis[v])

			{

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

				if(!vis[v])

				{

					vis[v]=1;

					q.push(v);

				}

			}

		}

	}

}

int main()

{

	scanf("%d",&k);

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

	{

		adj[i].push_back(edge((i+1)%k,1));

		adj[i].push_back(edge(i*10%k,0));

	}

	bfs();

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

	return 0;

}

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

using namespace std;

#define int long long

#define fi first

#define se second

#define mp make_pair

int n;

const int maxn=2e5+100;

int dist[maxn];

priority_queue < pair < int,int > > q;

bool used[maxn];

void solve(){

	cin >> n;

	memset(dist,10,sizeof(dist));

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

	dist[0]=0;

	while (!q.empty()){

		int u=-q.top().fi;

		int v=q.top().se;

//		cout << u << ' '<< v << endl;

		q.pop();

		if (dist[v]!=u) continue;

		used[v]=true;

		int tmp[2];tmp[1]=(v+1-1)%n+1;

		tmp[0]=(v*10-1)%n+1;

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

			if (!used[tmp[i]] && dist[tmp[i]]>u+i){

				dist[tmp[i]]=u+i;

				q.push(mp(-dist[tmp[i]],tmp[i]));

			}

		}

	}

	cout << dist[n] << endl;

}

signed main(){

	solve();

	return 0;

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

#include <cstdio>

#include <cstring>

#include <queue>



const int N = 2e5 + 52;

struct edge {

	int to, next, w;

} e[N << 4];

int n, head[N], cnt;

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



std::queue<int> q;

int dis[N];

int main() {

	memset(head, -1, sizeof head);

	memset(dis, 0x3f, sizeof dis), dis[1] = 1;

	scanf("%d", &n);

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

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

	for (int i = 1; i < 10; i++) q.push(i);

	for (; !q.empty(); q.pop())

		for (int x = q.front(), i = x[head], nx; ~i; i = e[i].next)

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

				nx[dis] = x[dis] + e[i].w, q.push(nx);

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

}

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

#include<cstdio>

#include<cstring>

using namespace std;

int mod,l,r,vis[100050];

struct node{

	long long tot,val;

}q[100050];

int main(){

	cin>>mod;

	q[l=r=1].tot=1;q[1].val=1;

	while(l<=r){

		

		if(!q[l].tot){

			cout<<q[l].val;return 0;

		}if(vis[q[l].tot]){

			++l;

		}else{

			vis[q[l].tot]=1;

			q[l].tot=q[l].tot*10%mod;q[l].val=q[l].val;

			q[++r].tot=(q[l].tot+1)%mod;q[r].val=q[l].val+1;

		}

	}

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

#define maxn 100005

#define ll long long

using namespace std;

int k;

int dis[maxn];

struct edge

{

	int v,w;

	edge(int v=0,int w=0):v(v),w(w){}

};

vector<edge>adj[maxn];

bool vis[maxn];

void bfs()

{

	queue<int>q;

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

	dis[1]=1;vis[1]=true;

	q.push(1);

	int u,v,w;

	while(!q.empty())

	{

		u=q.front();

		q.pop();

		vis[u]=0;

		int sz=adj[u].size();

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

		{

			v=adj[u][i].v;

			w=adj[u][i].w;

			if(dis[u]+w<dis[v])

			{

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

				if(!vis[v])

				{

					vis[v]=1;

					q.push(v);

				}

			}

		}

	}

}

int main()

{

	scanf("%d",&k);

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

	{

		adj[i].push_back(edge((i+1)%k,1));

		adj[i].push_back(edge(i*10%k,0));

	}

	bfs();

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

	return 0;

}

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

#include<cstdio>

#include<cstring>

using namespace std;

int mod,l,r,vis[100050];

struct node{

	long long tot,val;

}q[100050];

int main(){

	cin>>mod;

	q[l=r=1].tot=1;q[1].val=1;

	while(l<=r){

		

		if(!q[l].tot){

			cout<<q[l].val;return 0;

		}if(vis[q[l].tot]){

			++l;

		}else{

			vis[q[l].tot]=1;

			q[l].tot=q[l].tot*10%mod;q[l].val=q[l].val;

			q[++r].tot=(q[l].tot+1)%mod;q[r].val=q[l].val+1;

		}

	}

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

using namespace std;

#define int long long

#define fi first

#define se second

#define mp make_pair

int n;

const int maxn=2e5+100;

int dist[maxn];

priority_queue < pair < int,int > > q;

bool used[maxn];

void solve(){

	cin >> n;

	memset(dist,10,sizeof(dist));

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

	dist[0]=0;

	while (!q.empty()){

		int u=-q.top().fi;

		int v=q.top().se;

//		cout << u << ' '<< v << endl;

		q.pop();

		if (dist[v]!=u) continue;

		used[v]=true;

		int tmp[2];tmp[1]=(v+1-1)%n+1;

		tmp[0]=(v*10-1)%n+1;

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

			if (!used[tmp[i]] && dist[tmp[i]]>u+i){

				dist[tmp[i]]=u+i;

				q.push(mp(-dist[tmp[i]],tmp[i]));

			}

		}

	}

	cout << dist[n] << endl;

}

signed main(){

	solve();

	return 0;

}

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

#include<cstdio>

#include<cstring>

using namespace std;

int mod,l,r,vis[100050];

struct node{

	long long tot,val;

}q[100050];

int main(){

	cin>>mod;

	q[l=r=1].tot=1;q[1].val=1;

	while(l<=r){

		

		if(!q[l].tot){

			cout<<q[l].val;return 0;

		}if(vis[q[l].tot]){

			++l;

		}else{

			vis[q[l].tot]=1;

			q[l].tot=q[l].tot*10%mod;q[l].val=q[l].val;

			q[++r].tot=(q[l].tot+1)%mod;q[r].val=q[l].val+1;

		}

	}

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

#include <cstdio>

#include <cstring>

#include <queue>



const int N = 2e5 + 52;

struct edge {

	int to, next, w;

} e[N << 4];

int n, head[N], cnt;

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



std::queue<int> q;

int dis[N];

int main() {

	memset(head, -1, sizeof head);

	memset(dis, 0x3f, sizeof dis), dis[1] = 1;

	scanf("%d", &n);

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

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

	for (int i = 1; i < 10; i++) q.push(i);

	for (; !q.empty(); q.pop())

		for (int x = q.front(), i = x[head], nx; ~i; i = e[i].next)

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

				nx[dis] = x[dis] + e[i].w, q.push(nx);

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

}

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <string>

#include <queue>

#include <deque>

#define N 101000

template<typename T> inline void read(T &x) {

	x = 0; char c = getchar(); bool flag = false;

	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }

	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }

	if (flag)	x = -x;

}

using namespace std;

int n;

int dis[N];

deque<int> q, qq;

inline void bfs() {

	q.push_back(1);

	qq.push_back(1);

	while (q.size()) {

		int p = q.front();

		q.pop_front();

		int v = qq.front();

		qq.pop_front();

		if (dis[p])	continue;

		dis[p] = v;

		if (!p)	return ;

		q.push_back((p + 1) % n);

		qq.push_back(dis[p] + 1);

		q.push_front(p * 10 % n);

		qq.push_front(dis[p]);

	}

}



int main() {

	read(n);

	bfs();

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

	return 0;

}

/*

6 3

41 5

79992 36

7 2(1001)

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

#define maxn 100005

#define ll long long

using namespace std;

int k;

int dis[maxn];

struct edge

{

	int v,w;

	edge(int v=0,int w=0):v(v),w(w){}

};

vector<edge>adj[maxn];

bool vis[maxn];

void bfs()

{

	queue<int>q;

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

	dis[1]=1;vis[1]=true;

	q.push(1);

	int u,v,w;

	while(!q.empty())

	{

		u=q.front();

		q.pop();

		vis[u]=0;

		int sz=adj[u].size();

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

		{

			v=adj[u][i].v;

			w=adj[u][i].w;

			if(dis[u]+w<dis[v])

			{

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

				if(!vis[v])

				{

					vis[v]=1;

					q.push(v);

				}

			}

		}

	}

}

int main()

{

	scanf("%d",&k);

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

	{

		adj[i].push_back(edge((i+1)%k,1));

		adj[i].push_back(edge(i*10%k,0));

	}

	bfs();

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

	return 0;

}

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <string>

#include <queue>

#include <deque>

#define N 101000

template<typename T> inline void read(T &x) {

	x = 0; char c = getchar(); bool flag = false;

	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }

	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }

	if (flag)	x = -x;

}

using namespace std;

int n;

int dis[N];

deque<int> q, qq;

inline void bfs() {

	q.push_back(1);

	qq.push_back(1);

	while (q.size()) {

		int p = q.front();

		q.pop_front();

		int v = qq.front();

		qq.pop_front();

		if (dis[p])	continue;

		dis[p] = v;

		if (!p)	return ;

		q.push_back((p + 1) % n);

		qq.push_back(dis[p] + 1);

		q.push_front(p * 10 % n);

		qq.push_front(dis[p]);

	}

}



int main() {

	read(n);

	bfs();

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

	return 0;

}

/*

6 3

41 5

79992 36

7 2(1001)

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

using namespace std;

#define int long long

#define fi first

#define se second

#define mp make_pair

int n;

const int maxn=2e5+100;

int dist[maxn];

priority_queue < pair < int,int > > q;

bool used[maxn];

void solve(){

	cin >> n;

	memset(dist,10,sizeof(dist));

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

	dist[0]=0;

	while (!q.empty()){

		int u=-q.top().fi;

		int v=q.top().se;

//		cout << u << ' '<< v << endl;

		q.pop();

		if (dist[v]!=u) continue;

		used[v]=true;

		int tmp[2];tmp[1]=(v+1-1)%n+1;

		tmp[0]=(v*10-1)%n+1;

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

			if (!used[tmp[i]] && dist[tmp[i]]>u+i){

				dist[tmp[i]]=u+i;

				q.push(mp(-dist[tmp[i]],tmp[i]));

			}

		}

	}

	cout << dist[n] << endl;

}

signed main(){

	solve();

	return 0;

}

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

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <string>

#include <queue>

#include <deque>

#define N 101000

template<typename T> inline void read(T &x) {

	x = 0; char c = getchar(); bool flag = false;

	while (!isdigit(c)) {if (c == '-') flag = true; c = getchar(); }

	while (isdigit(c)) {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }

	if (flag)	x = -x;

}

using namespace std;

int n;

int dis[N];

deque<int> q, qq;

inline void bfs() {

	q.push_back(1);

	qq.push_back(1);

	while (q.size()) {

		int p = q.front();

		q.pop_front();

		int v = qq.front();

		qq.pop_front();

		if (dis[p])	continue;

		dis[p] = v;

		if (!p)	return ;

		q.push_back((p + 1) % n);

		qq.push_back(dis[p] + 1);

		q.push_front(p * 10 % n);

		qq.push_front(dis[p]);

	}

}



int main() {

	read(n);

	bfs();

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

	return 0;

}

/*

6 3

41 5

79992 36

7 2(1001)

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

#include <vector>

#include <queue>

#include <algorithm>

#define MAX_V 200000

#define INF 1 << 29

using namespace std;

typedef long long ll;

typedef pair<ll, int> pli;

struct Edge {

    int to;

    ll cost;

};

vector<Edge> g[MAX_V];

ll d[MAX_V];

void solve() {

    d[0] = 0;

    queue<pli> q;

    q.push(pli(0LL, 0));

    while (!q.empty()) {

        pli p = q.front(); q.pop();

        int v = p.second;

        for (size_t i = 0U; i < g[v].size(); ++i) {

            Edge e = g[v][i];

            if (d[e.to] > e.cost + d[v]) {

                d[e.to] = e.cost + d[v];

                q.push(pli(d[e.to], e.to));

            }

        }

    }

}

int main(void) {

    int k; cin >> k;

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

        d[i] = INF;

    }

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

        Edge e = { i + 1, 1LL };

        g[i].push_back(e);

    }

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

        Edge e = { i * 10 % k, 0LL };

        if (e.to == 0) e.to = k;

        g[i].push_back(e);

    }

    solve();

    cout << d[k] << endl;

    return 0;

}










































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

using namespace std;

const int INF = 1e9;

int k;

int ary[100005];

void solve(int p, int q) {

    if (ary[p] <= q) return;

    ary[p] = q;

    solve(p * 10 % k, q);

    solve((p + 1) % k, q + 1);

}

int main(void) {

    cin >> k;

    for (int i = 0; i < k; ++i) ary[i] = 45;

    solve(1, 1);

    cout << ary[0] << endl;

    return 0;

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

#include <cstring>

#include <sstream>

#include <algorithm>

#include <vector>

using namespace std;



#define min(a,b) (a<b?a:b)

#define mem(a,n) memset(a,sizeof(a),n)

typedef long long ll;

const int mod=1e9+7;

const int N=1e5+5;

const int INF=0x3f3f3f3f;

bool vis[N][100];



int digit_sum(int x)

{

    int sum=0;

    while(x)

    {

        sum+=(x%10);

        x/=10;

    }

    return sum;

}

int n;

void dfs(int x,int sum)

{

    if(sum>=99||vis[x][sum]) return;

    vis[x][sum]=1;

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

        dfs((10*x+i)%n,sum+i);

}



int main()

{

    while(~scanf("%d",&n))

    {

        mem(vis,0);

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

            dfs(i,digit_sum(i));

        int ans=INF;

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

            if(vis[0][i])

                ans=min(ans,i);

        printf("%d\n",ans);

    }

    return 0;

}

/**

2

1 5

2 4

3 6

3

1 1 1

2 2 2

3 3 3

6

3 14 159 2 6 53

58 9 79 323 84 6

2643 383 2 79 50 288

**/


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

#include <cstring>

#include <sstream>

#include <algorithm>

#include <vector>

using namespace std;



#define min(a,b) (a<b?a:b)

#define mem(a,n) memset(a,sizeof(a),n)

typedef long long ll;

const int mod=1e9+7;

const int N=1e5+5;

const int INF=0x3f3f3f3f;

bool vis[N][100];



int digit_sum(int x)

{

    int sum=0;

    while(x)

    {

        sum+=(x%10);

        x/=10;

    }

    return sum;

}

int n;

void dfs(int x,int sum)

{

    if(sum>=80||vis[x][sum]) return;

    vis[x][sum]=1;

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

        dfs((10*x+i)%n,sum+i);

}



int main()

{

    while(~scanf("%d",&n))

    {

       // printf("n=%d\n",n);

        mem(vis,0);

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

            dfs(i,digit_sum(i));

        int ans=INF;

       // printf("%d\n",ans);

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

            if(vis[0][i])

                ans=min(ans,i);

        printf("%d\n",ans);

    }

    return 0;

}

/**

2

1 5

2 4

3 6

3

1 1 1

2 2 2

3 3 3

6

3 14 159 2 6 53

58 9 79 323 84 6

2643 383 2 79 50 288

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

using namespace std;

const int N=1e5+7;

const int INF=0x3f;

int m,n,k,p,cnt;

int dis[N],head[N];

struct edge

{

    int nx,to,dist;

} e[N*40];

void add_edge(int a,int b,int dist)

{

    cnt++;e[cnt].nx=head[a];e[cnt].to=b;e[cnt].dist=dist;head[a]=cnt;

}

struct node

{

    int pos,dist;

    bool operator<(const node &x) const

    {

        return x.dist<dist;

    }

};

priority_queue<node> que;

bool vis[N];

void dijkstra(int pos)

{

    for (int i=1;i<=N;i++) dis[i]=INF;

    que.push((node){pos,0});dis[pos]=0;

    while (!que.empty())

    {

        node tmp=que.top();que.pop();

        int x=tmp.pos;

        if (vis[x]) continue;

        vis[x]=true;

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

        {

            int y=e[i].to;

            if (dis[y]>dis[x]+e[i].dist)

            {

                dis[y]=dis[x]+e[i].dist;

                if  (!vis[y]) que.push((node) {y,dis[y]});

            }

        }

    }

}

int main()

{

	scanf("%d",&n);

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

	{

		for (int j=0;j<=9;j++)

		add_edge(i,((i-1)*10+j)%n+1,j);

	}

	for (int j=1;j<=9;j++) add_edge(0,j+1,j);

	dijkstra(0);

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

	return 0;

}

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

using namespace std;

typedef pair<int,int> P;

int n,m,k; 

deque <P> q;

int vis[100005];

int main()

{

	cin>>k;

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

	while(!q.empty())

	{

		P top=q.front();

		//cout<<top.first<<" "<<top.second<<endl; 

		q.pop_front();

		if(vis[top.first]) continue;

        vis[top.first]=1;

		if(top.first==0)

		{

			cout<<top.second<<endl;

			return 0;

		}

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

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

	}

	return 0;

}
// Slower C++ solution:
/*

Problem : atcoder 084D

Algorithm : dijkstra

Status :

*/

#include <bits/stdc++.h>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5;



int n,len;

int head[MAXN],dis[MAXN],vis[MAXN];

priority_queue<pii,vector<pii>,greater<pii> > q;



struct Edge{

	int to,next,w;

} e[MAXN * 2];



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

	e[++len].to = v;

	e[len].next = head[u];

	e[len].w = w;

	head[u] = len;

}



int main(){

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

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

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

	scanf("%d",&n);

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

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

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

		dis[i] = INF;

	}

	dis[1] = 1;

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

	while(!q.empty()){

		int u = q.top().second;

		q.pop();

		if(vis[u])

		    continue;

		vis[u] = true;

		for(int i = head[u];i != -1;i = e[i].next){

			int v = e[i].to;

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

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

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

			}

		}

	}

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

	return 0;

}




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

using namespace std;

typedef pair<int,int> P;

int n,m,k; 

deque <P> q;

int vis[100005];

int main()

{

	cin>>k;

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

	while(!q.empty())

	{

		P top=q.front();

		//cout<<top.first<<" "<<top.second<<endl; 

		q.pop_front();

		if(vis[top.first]) continue;

        vis[top.first]=1;

		if(top.first==0)

		{

			cout<<top.second<<endl;

			return 0;

		}

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

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

	}

	return 0;

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

using namespace std;

const int N=1e5+7;

const int INF=0x3f;

int m,n,k,p,cnt;

int dis[N],head[N];

struct edge

{

    int nx,to,dist;

} e[N*40];

void add_edge(int a,int b,int dist)

{

    cnt++;e[cnt].nx=head[a];e[cnt].to=b;e[cnt].dist=dist;head[a]=cnt;

}

struct node

{

    int pos,dist;

    bool operator<(const node &x) const

    {

        return x.dist<dist;

    }

};

priority_queue<node> que;

bool vis[N];

void dijkstra(int pos)

{

    for (int i=1;i<=N;i++) dis[i]=INF;

    que.push((node){pos,0});dis[pos]=0;

    while (!que.empty())

    {

        node tmp=que.top();que.pop();

        int x=tmp.pos;

        if (vis[x]) continue;

        vis[x]=true;

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

        {

            int y=e[i].to;

            if (dis[y]>dis[x]+e[i].dist)

            {

                dis[y]=dis[x]+e[i].dist;

                if  (!vis[y]) que.push((node) {y,dis[y]});

            }

        }

    }

}

int main()

{

	scanf("%d",&n);

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

	{

		for (int j=0;j<=9;j++)

		add_edge(i,((i-1)*10+j)%n+1,j);

	}

	for (int j=1;j<=9;j++) add_edge(0,j+1,j);

	dijkstra(0);

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

	return 0;

}

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

#include <cstring>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <queue>

#define INF 1000000000

#define M 1000005

using namespace std;

int k,nxt[M],head[M],to[M],adj[M],dist[M],tot;

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

	nxt[++tot]=head[u];head[u]=tot;to[tot]=v;adj[tot]=w;

	return;

}

struct node{

	int dis,id;

	bool operator< (const node b) const{return dis<b.dis;}

	bool operator> (const node b) const{return dis>b.dis;}

};

int dijkstra(){

	priority_queue <node,vector<node>,greater<node> > Q;

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

	dist[2]=1;Q.push((node){1,2});

	while (!Q.empty()){

		node now=Q.top();Q.pop();

		if (now.dis!=dist[now.id]) continue;

		for (register int i=head[now.id];i;i=nxt[i])

			if (dist[to[i]]>now.dis+adj[i]){

				dist[to[i]]=now.dis+adj[i];

				Q.push((node){dist[to[i]],to[i]});

			}

	}

	return dist[1];

}

int main(){

	scanf("%d",&k);

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

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

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

	}

	printf("%d",dijkstra());

	return 0;

}