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

#define int long long

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

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

#define cauto const auto &

#define cint const int &

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

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

using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3f;

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

inline int read()

{

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

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

  {

    if (c == '-')

    {

      y = -1;

    }

    c = getchar();

  }

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

  {

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

    c = getchar();

  }

  return x * y;

}

/*

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

*/

struct road{

    int to,v;

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

};



static vector<road> edge[MAXN];

struct heapnode{

    int to,val;

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

    bool operator<(const heapnode r)const{

        return val>r.val;

    }

};

static priority_queue<heapnode> q;

static int d[MAXN];

void dijkstra(){

    ini(d,0x3f);

    d[0]=0;

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

    while(!q.empty()){

        int pos=q.top().to;

        q.pop();

        for(auto to:edge[pos]){



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

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

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

            }

        }

    }

}

signed main(){

    int k=read();

    F(i,1,k-1){

        int now=i;

        F(j,1,9){

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

            now*=10;

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

        }

    }

    dijkstra();

//    int minn=INF;

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

    return 0;

}


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

using namespace std;

#define fi			first

#define se			second

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

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

#define put(x)		putchar(x)

#define eoln        put('\n')

#define space		put(' ')

inline int read(){

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

	while(!isdigit(c)){

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

		c=getchar();

	}

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

	return x*neg;

}

inline void print(int x){

	if(x<0){

		putchar('-');

		print(abs(x));

		return;

	}

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

	else{

		print(x/10);

		putchar(x%10+'0');

	}

}

int n=read();

struct edge{

	int u,v,w;

};

vector<edge> g[100005];

int dist[100005];

inline void dijkstra(){

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

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

	dist[1]=1;

	pq.push({1,1});

	while(!pq.empty()){

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

		pq.pop();

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

		if(s>dist[x])	continue;

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

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

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

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

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

			}

		}

	}

}

int main(){

	fz(i,0,n-1){

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

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

	}

	dijkstra();

	print(dist[0]);

	return 0;

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

}

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

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

}


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

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

using namespace std;

int read()

{

    int d = 0, w = 1;

    char ch = getchar();

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

        ch = getchar();

    if (ch == '-')

        w = -1, ch = getchar();

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

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

    return d * w;

}

void write_(int x)

{

    if (x < 0)

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

    if (x > 9)

        write_(x / 10);

    putchar(x % 10 + '0');

}

void writeln(int x)

{

    write_(x);

    putchar('\n');

}

void writesp(int x)

{

    write_(x);

    putchar(' ');

}

int vis[111000];

int main()

{

#ifdef __clang__

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

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

#endif

    using P = pair<int, int>;

    int K = read();

    deque<P> de;

    de.push_back({1, 1});

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

    while(1)

    {

        P p = de.back();

        de.pop_back();

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

            continue;

        vis[p.first] = p.second;

        if(p.first == 0)

        {

            writeln(p.second);

            return 0;

        }

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

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

    }

    return 0;

}

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

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

#define int long long

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

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

#define cauto const auto &

#define cint const int &

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

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

using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3f;

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

inline int read()

{

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

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

  {

    if (c == '-')

    {

      y = -1;

    }

    c = getchar();

  }

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

  {

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

    c = getchar();

  }

  return x * y;

}

/*

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

*/

struct road{

    int to,v;

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

};



static vector<road> edge[MAXN];

struct heapnode{

    int to,val;

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

    bool operator<(const heapnode r)const{

        return val>r.val;

    }

};

static priority_queue<heapnode> q;

static int d[MAXN];

void dijkstra(){

    ini(d,0x3f);

    d[0]=0;

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

    while(!q.empty()){

        int pos=q.top().to;

        q.pop();

        for(auto to:edge[pos]){



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

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

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

            }

        }

    }

}

signed main(){

    int k=read();

    F(i,1,k-1){

        int now=i;

        F(j,1,9){

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

            now*=10;

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

        }

    }

    dijkstra();

//    int minn=INF;

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

    return 0;

}


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

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

using namespace std;



const int N=200200,inf=0x3f3f3f3f;



int k;



struct edge

{

	int from,to,w,nextt;

}g[N];

int head[N],cnt=0;

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

{

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

}



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

void spfa()

{

	memset(dist,0x3f,sizeof dist);

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

	while (!q.empty())

	{

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

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

		{

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

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

			{

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

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

			}

		}

			

	}

}





int main()

{

	cin>>k;

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

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

	spfa();

	cout<<dist[0]+1;

	return 0;

}

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

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

using namespace std ;

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

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

#define re register

int gi() {

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

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

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

	return cn * flus ;

}

const int M = 1e5 + 5 ; 

struct E {

	int to, next, w ;

} e[M * 20] ; 

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

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

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

}

queue<int> q ;

void spfa() {

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

	rep( i, 1, 9 ) {

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

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

	}

	while( !q.empty() ) {

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

		Next( i, u ) {

			int v = e[i].to ; 

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

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

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

			}

		}

	}

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

}

signed main()

{

	n = gi() ; 

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

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

	spfa() ; 

	return 0 ;

}


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

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

using namespace std;

#define fi			first

#define se			second

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

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

#define put(x)		putchar(x)

#define eoln        put('\n')

#define space		put(' ')

inline int read(){

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

	while(!isdigit(c)){

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

		c=getchar();

	}

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

	return x*neg;

}

inline void print(int x){

	if(x<0){

		putchar('-');

		print(abs(x));

		return;

	}

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

	else{

		print(x/10);

		putchar(x%10+'0');

	}

}

int n=read();

struct edge{

	int u,v,w;

};

vector<edge> g[100005];

int dist[100005];

inline void dijkstra(){

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

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

	dist[1]=1;

	pq.push({1,1});

	while(!pq.empty()){

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

		pq.pop();

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

		if(s>dist[x])	continue;

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

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

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

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

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

			}

		}

	}

}

int main(){

	fz(i,0,n-1){

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

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

	}

	dijkstra();

	print(dist[0]);

	return 0;

}

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

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

}

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

#include<queue>

using namespace std;

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

struct bian{

	int to;

	int cost;

    int next;

}edge[200001];

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

{

	edge[++cnt].to=v;

	edge[cnt].cost=cost;

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

	head[u]=cnt;

}

int main()

{

	cin>>k;

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

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

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

	queue <int> q;

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

	while(!q.empty())

	{

		int from=q.front();

		q.pop();

		inqueue[from]=0;

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

		{

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

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

			{

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

				if(inqueue[to]==0)

				{

					inqueue[to]=1;

					q.push(to);

				}

		    }

		}

	}

	cout<<dis[0]<<endl;

	return 0;

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

#define int long long

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

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

#define cauto const auto &

#define cint const int &

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

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

using namespace std;

const int INF = 0x3f3f3f3f3f3f3f3f;

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

inline int read()

{

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

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

  {

    if (c == '-')

    {

      y = -1;

    }

    c = getchar();

  }

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

  {

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

    c = getchar();

  }

  return x * y;

}

/*

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

*/

struct road{

    int to,v;

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

};



static vector<road> edge[MAXN];

struct heapnode{

    int to,val;

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

    bool operator<(const heapnode r)const{

        return val>r.val;

    }

};

static priority_queue<heapnode> q;

static int d[MAXN];

void dijkstra(){

    ini(d,0x3f);

    d[0]=0;

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

    while(!q.empty()){

        int pos=q.top().to;

        q.pop();

        for(auto to:edge[pos]){



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

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

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

            }

        }

    }

}

signed main(){

    int k=read();

    F(i,1,k-1){

        int now=i;

        F(j,1,9){

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

            now*=10;

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

        }

    }

    dijkstra();

//    int minn=INF;

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

    return 0;

}


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

#include<queue>

using namespace std;

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

struct bian{

	int to;

	int cost;

    int next;

}edge[200001];

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

{

	edge[++cnt].to=v;

	edge[cnt].cost=cost;

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

	head[u]=cnt;

}

int main()

{

	cin>>k;

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

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

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

	queue <int> q;

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

	while(!q.empty())

	{

		int from=q.front();

		q.pop();

		inqueue[from]=0;

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

		{

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

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

			{

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

				if(inqueue[to]==0)

				{

					inqueue[to]=1;

					q.push(to);

				}

		    }

		}

	}

	cout<<dis[0]<<endl;

	return 0;

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

using namespace std;

#define fi			first

#define se			second

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

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

#define put(x)		putchar(x)

#define eoln        put('\n')

#define space		put(' ')

inline int read(){

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

	while(!isdigit(c)){

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

		c=getchar();

	}

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

	return x*neg;

}

inline void print(int x){

	if(x<0){

		putchar('-');

		print(abs(x));

		return;

	}

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

	else{

		print(x/10);

		putchar(x%10+'0');

	}

}

int n=read();

struct edge{

	int u,v,w;

};

vector<edge> g[100005];

int dist[100005];

inline void dijkstra(){

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

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

	dist[1]=1;

	pq.push({1,1});

	while(!pq.empty()){

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

		pq.pop();

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

		if(s>dist[x])	continue;

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

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

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

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

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

			}

		}

	}

}

int main(){

	fz(i,0,n-1){

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

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

	}

	dijkstra();

	print(dist[0]);

	return 0;

}

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

#include<queue>

using namespace std;

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

struct bian{

	int to;

	int cost;

    int next;

}edge[200001];

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

{

	edge[++cnt].to=v;

	edge[cnt].cost=cost;

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

	head[u]=cnt;

}

int main()

{

	cin>>k;

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

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

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

	queue <int> q;

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

	while(!q.empty())

	{

		int from=q.front();

		q.pop();

		inqueue[from]=0;

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

		{

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

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

			{

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

				if(inqueue[to]==0)

				{

					inqueue[to]=1;

					q.push(to);

				}

		    }

		}

	}

	cout<<dis[0]<<endl;

	return 0;

}