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

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

using namespace std;

const int INF=1<<29;

/*

Status:Writing

Type:Problemset/HB

Problem ID:Atcoder/ARC/84

Author:XIZCM

*/

int k;

deque<int> dq;

int d[100005];

int main(){

	cin>>k;

	fill(d,d+100005,INF);

	d[1]=1;

	dq.push_front(1);

	while(!dq.empty()){

		int t=dq.front();

		dq.pop_front();

		if(d[(t*10)%k]>d[t]){

			d[(t*10)%k]=d[t];

			dq.push_front((t*10)%k);

		}

		if(d[(t+1)%k]>d[t]+1){

			d[(t+1)%k]=d[t]+1;

			dq.push_back((t+1)%k);

		}

	}

	cout<<d[0]<<endl;

	return 0;

}


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

using namespace std;

int k,l=1,r=1,a1,a2;

bool vis[100005];

typedef pair<int, int> P;

deque<P> que;

int main()

{

    scanf("%d",&k);que.push_back(make_pair(1, 1));

    while(!que.empty())

    {

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

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

        if(x.first==0){printf("%d",x.second);return 0;}

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

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

    }

    return 0;

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

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

using namespace std;

const int INF=1<<29;

/*

Status:Writing

Type:Problemset/HB

Problem ID:Atcoder/ARC/84

Author:XIZCM

*/

int k;

deque<int> dq;

int d[100005];

int main(){

	cin>>k;

	fill(d,d+100005,INF);

	d[1]=1;

	dq.push_front(1);

	while(!dq.empty()){

		int t=dq.front();

		dq.pop_front();

		if(d[(t*10)%k]>d[t]){

			d[(t*10)%k]=d[t];

			dq.push_front((t*10)%k);

		}

		if(d[(t+1)%k]>d[t]+1){

			d[(t+1)%k]=d[t]+1;

			dq.push_back((t+1)%k);

		}

	}

	cout<<d[0]<<endl;

	return 0;

}


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

#define ll long long

using namespace std;

const int N = 100001;

struct node{

    int v,nxt,cost;

}edge[N<<1];

int head[N],k,tot;

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

int dist[N];

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

    edge[++tot].v=v;

    edge[tot].cost=val;

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

    head[u]=tot;

}

int main() {

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

    scanf("%d",&k);

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

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

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

        dist[i]=N;

    }

    dist[1]=0;

    l=-1;

    r=0;

    q[0]=1;

    while (l<r) {

        u = q[++l];

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

            v=edge[i].v;

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

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

                q[++r]=v;

            }

        }

    }

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

    return 0;

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

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

using namespace std;

const int INF=1<<29;

/*

Status:Writing

Type:Problemset/HB

Problem ID:Atcoder/ARC/84

Author:XIZCM

*/

int k;

deque<int> dq;

int d[100005];

int main(){

	cin>>k;

	fill(d,d+100005,INF);

	d[1]=1;

	dq.push_front(1);

	while(!dq.empty()){

		int t=dq.front();

		dq.pop_front();

		if(d[(t*10)%k]>d[t]){

			d[(t*10)%k]=d[t];

			dq.push_front((t*10)%k);

		}

		if(d[(t+1)%k]>d[t]+1){

			d[(t+1)%k]=d[t]+1;

			dq.push_back((t+1)%k);

		}

	}

	cout<<d[0]<<endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.4032619804770967x):
/*

  code by RyeCatcher

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <utility>

#include <queue>

#include <vector>

#include <ext/pb_ds/hash_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

#include <iostream>

#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define ri register int

#define ll long long

#define ull unsigned long long

#define SIZE 1<<22

using std::min;

using std::max;

using std::deque;

using std::vector;

using std::pair;

using namespace __gnu_pbds;

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

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

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn = 10000005;

const int inf=0x7fffffff;

typedef pair<int,int> pii;

bool vis[maxn];

deque<pii>q;

int k;

int main(){

	int x,y;

	read(k);

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

	while(q.size()){

		x=q.front().first,y=q.front().second;q.pop_front();

		if(vis[x])continue;vis[x]=1;

		if(x==0){

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

			break;

		}

		q.push_front(pii(x*10%k,y));

		q.push_back(pii((x+1)%k,y+1));

	}

	return 0;

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

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cctype>

#include<queue>

#include<vector>

inline int read() {

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

	for (; !isdigit(c); c = getchar()) f ^= c == '-';

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

	return f ? x : -x;

}

using namespace std;

const int yuzu = 1e5;

int d[yuzu | 10],k;



void bfs(int u, int dep) {

	memset(d, 0x3f, sizeof d);

	queue<int> q;

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

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

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

		int net = u * 10 % k;

		if (d[net] > d[u]) {

			q.push(net);

			d[net] = d[u];

		}

		net = (u + 1) % k;

		if (d[net] > d[u] + 1) {

			q.push(net);

			d[net] = d[u] + 1;

		}

	}

}



int main() {

	k = read();

	bfs(1, 1);

	cout << d[0]<<endl;

}

// Faster C++ solution for the same problem (measured speedup: 1.4972957621609948x):
/*

  code by RyeCatcher

*/

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <utility>

#include <queue>

#include <vector>

#include <ext/pb_ds/hash_policy.hpp>

#include <ext/pb_ds/assoc_container.hpp>

#include <iostream>

#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);

#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}

#define ri register int

#define ll long long

#define ull unsigned long long

#define SIZE 1<<22

using std::min;

using std::max;

using std::deque;

using std::vector;

using std::pair;

using namespace __gnu_pbds;

inline char gc(){

    static char buf[SIZE],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;

}

#define gc getchar

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

    x=0;int ne=0;char c;

    while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;

    while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;

}

const int maxn = 10000005;

const int inf=0x7fffffff;

typedef pair<int,int> pii;

bool vis[maxn];

deque<pii>q;

int k;

int main(){

	int x,y;

	read(k);

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

	while(q.size()){

		x=q.front().first,y=q.front().second;q.pop_front();

		if(vis[x])continue;vis[x]=1;

		if(x==0){

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

			break;

		}

		q.push_front(pii(x*10%k,y));

		q.push_back(pii((x+1)%k,y+1));

	}

	return 0;

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

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

using namespace std;

const int INF=1<<29;

/*

Status:Writing

Type:Problemset/HB

Problem ID:Atcoder/ARC/84

Author:XIZCM

*/

int k;

deque<int> dq;

int d[100005];

int main(){

	cin>>k;

	fill(d,d+100005,INF);

	d[1]=1;

	dq.push_front(1);

	while(!dq.empty()){

		int t=dq.front();

		dq.pop_front();

		if(d[(t*10)%k]>d[t]){

			d[(t*10)%k]=d[t];

			dq.push_front((t*10)%k);

		}

		if(d[(t+1)%k]>d[t]+1){

			d[(t+1)%k]=d[t]+1;

			dq.push_back((t+1)%k);

		}

	}

	cout<<d[0]<<endl;

	return 0;

}


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

const int N = 1e5+9;

using namespace std;

deque<pair<int, long long> > q;

int k;

bool vis[N];



int main() {

  scanf("%d", &k);

  q.push_back({1, 1});

  while(!q.empty()) {

    pair<int, long long> tp = q.front(); q.pop_front();

    if(!tp.first) {

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

      break;

    }

    if(vis[tp.first]) continue;

    vis[tp.first] = 1;

    q.push_front({tp.first*10%k, tp.second});

    q.push_back({(tp.first+1)%k, tp.second+1});

  }

  return 0;

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

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cctype>

#include<queue>

#include<vector>

inline int read() {

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

	for (; !isdigit(c); c = getchar()) f ^= c == '-';

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

	return f ? x : -x;

}

using namespace std;

const int yuzu = 1e5;

int d[yuzu | 10],k;



void bfs(int u, int dep) {

	memset(d, 0x3f, sizeof d);

	queue<int> q;

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

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

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

		int net = u * 10 % k;

		if (d[net] > d[u]) {

			q.push(net);

			d[net] = d[u];

		}

		net = (u + 1) % k;

		if (d[net] > d[u] + 1) {

			q.push(net);

			d[net] = d[u] + 1;

		}

	}

}



int main() {

	k = read();

	bfs(1, 1);

	cout << d[0]<<endl;

}

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

const int N = 1e5+9;

using namespace std;

deque<pair<int, long long> > q;

int k;

bool vis[N];



int main() {

  scanf("%d", &k);

  q.push_back({1, 1});

  while(!q.empty()) {

    pair<int, long long> tp = q.front(); q.pop_front();

    if(!tp.first) {

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

      break;

    }

    if(vis[tp.first]) continue;

    vis[tp.first] = 1;

    q.push_front({tp.first*10%k, tp.second});

    q.push_back({(tp.first+1)%k, tp.second+1});

  }

  return 0;

}
// Slower C++ solution:
#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;  

} 

// Faster C++ solution for the same problem (measured speedup: 1.3218999597634435x):
#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)
// Slower C++ solution:


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

}

// Faster C++ solution for the same problem (measured speedup: 1.322034914980648x):
#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)
// Slower C++ solution:
#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;  

} 

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

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

#include <vector>

#include <queue>

#include <cmath>

#include <map>

#include <set>



typedef long long ll;

using namespace std;

const int maxn = 2e5+10;

const int maxm = 4e6+10;

const double eps = 1e-5;

const int mod = 1e9+7;



int dis[maxn];

bool vis[maxn];

deque<int> q;

int main() {

#ifdef LOCAL

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

#endif // local

    ios::sync_with_stdio(false);

    cin.tie(0);

    int k;

    cin>>k;

    dis[1]=1;

    q.push_front(1);

    while(!q.empty()) {

        int tmp=q.front();

        q.pop_front();

        if(vis[tmp]) continue;

        vis[tmp]=true;

        if(tmp==0) break;

        if(!dis[tmp*10%k]||dis[tmp*10%k]>dis[tmp]) {

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

            q.push_front(tmp*10%k);

        }

        if(!dis[(tmp+1)%k]||dis[(tmp+1)%k]>dis[tmp]+1) {

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

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

        }

    }

    cout<<dis[0]<<endl;

    return 0;

}
// Slower C++ solution:


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

}

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

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

#include <vector>

#include <queue>

#include <cmath>

#include <map>

#include <set>



typedef long long ll;

using namespace std;

const int maxn = 2e5+10;

const int maxm = 4e6+10;

const double eps = 1e-5;

const int mod = 1e9+7;



int dis[maxn];

bool vis[maxn];

deque<int> q;

int main() {

#ifdef LOCAL

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

#endif // local

    ios::sync_with_stdio(false);

    cin.tie(0);

    int k;

    cin>>k;

    dis[1]=1;

    q.push_front(1);

    while(!q.empty()) {

        int tmp=q.front();

        q.pop_front();

        if(vis[tmp]) continue;

        vis[tmp]=true;

        if(tmp==0) break;

        if(!dis[tmp*10%k]||dis[tmp*10%k]>dis[tmp]) {

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

            q.push_front(tmp*10%k);

        }

        if(!dis[(tmp+1)%k]||dis[(tmp+1)%k]>dis[tmp]+1) {

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

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

        }

    }

    cout<<dis[0]<<endl;

    return 0;

}
// Slower C++ solution:
#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;

}

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

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

#include <vector>

#include <queue>

#include <cmath>

#include <map>

#include <set>



typedef long long ll;

using namespace std;

const int maxn = 2e5+10;

const int maxm = 4e6+10;

const double eps = 1e-5;

const int mod = 1e9+7;



int dis[maxn];

bool vis[maxn];

deque<int> q;

int main() {

#ifdef LOCAL

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

#endif // local

    ios::sync_with_stdio(false);

    cin.tie(0);

    int k;

    cin>>k;

    dis[1]=1;

    q.push_front(1);

    while(!q.empty()) {

        int tmp=q.front();

        q.pop_front();

        if(vis[tmp]) continue;

        vis[tmp]=true;

        if(tmp==0) break;

        if(!dis[tmp*10%k]||dis[tmp*10%k]>dis[tmp]) {

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

            q.push_front(tmp*10%k);

        }

        if(!dis[(tmp+1)%k]||dis[(tmp+1)%k]>dis[tmp]+1) {

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

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

        }

    }

    cout<<dis[0]<<endl;

    return 0;

}
// Slower C++ solution:
#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;

}


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

#include <cstdio>

#include <algorithm>

#include <string.h>

#include <string>

#include <vector>

#include <queue>

#include <cmath>

#include <map>

#include <set>



typedef long long ll;

using namespace std;

const int maxn = 2e5+10;

const int maxm = 4e6+10;

const double eps = 1e-5;

const int mod = 1e9+7;



int dis[maxn];

bool vis[maxn];

deque<int> q;

int main() {

#ifdef LOCAL

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

#endif // local

    ios::sync_with_stdio(false);

    cin.tie(0);

    int k;

    cin>>k;

    dis[1]=1;

    q.push_front(1);

    while(!q.empty()) {

        int tmp=q.front();

        q.pop_front();

        if(vis[tmp]) continue;

        vis[tmp]=true;

        if(tmp==0) break;

        if(!dis[tmp*10%k]||dis[tmp*10%k]>dis[tmp]) {

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

            q.push_front(tmp*10%k);

        }

        if(!dis[(tmp+1)%k]||dis[(tmp+1)%k]>dis[tmp]+1) {

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

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

        }

    }

    cout<<dis[0]<<endl;

    return 0;

}
// Slower C++ solution:
#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;  

} 

// Faster C++ solution for the same problem (measured speedup: 1.2728196391052036x):
#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));

	}

}