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

#define mem(i,j) memset(i,j,sizeof(i))

#define pl (p<<1)

#define pr (p<<1)|1

#define int long long

using namespace std;

inline int read(){

	char ch=' ';int res=0,f=1;

	while(!isdigit(ch)){ch=getchar();if(ch=='-')f=-1;}

	while(isdigit(ch)){res=res*10+ch-'0';ch=getchar();}

	return res*f;

}

int _min(int x,int y){return x<y?x:y;}

int _max(int x,int y){return x>y?x:y;}

const int N=1e6+5;

int k,vis[N];

struct node{

	int x,ans;

};

#undef int

int main() {

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

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

	k=read();

	deque<node>q;

	q.push_front({1,1});

	while(!q.empty()){

		node kk=q.front();

		q.pop_front();

		if(vis[kk.x])continue;

		vis[kk.x]=1;

		if(!kk.x){

			printf("%lld\n",kk.ans);

			return 0;

		}

		q.push_front({(kk.x*10)%k,kk.ans});

		q.push_back({(kk.x+1)%k,kk.ans+1});

	}

	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: 3.4150511982467155x):
#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 ;

}
// 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: 3.222451089542085x):
#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 ;

}
// 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: 1.0453250768906048x):
#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 ;

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

const int N = 100000+5;

using namespace std;

int vis[N];

int main() {

    int n;

    scanf("%d",&n);

    deque<pair<int,int> > Q;

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

    while(!Q.empty()){

        pair<int,int> temp=Q.front();

        Q.pop_front();

        if(!vis[temp.first]){

            vis[temp.first]=true;

            if(temp.first==0){

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

                break;

            }

            Q.push_front(make_pair((temp.first*10)%n,temp.second));

            Q.push_back(make_pair((temp.first+1)%n,temp.second+1));

        }

    }

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

const int N = 100000+5;

using namespace std;

int vis[N];

int main() {

    int n;

    scanf("%d",&n);

    deque<pair<int,int> > Q;

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

    while(!Q.empty()){

        pair<int,int> temp=Q.front();

        Q.pop_front();

        if(!vis[temp.first]){

            vis[temp.first]=true;

            if(temp.first==0){

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

                break;

            }

            Q.push_front(make_pair((temp.first*10)%n,temp.second));

            Q.push_back(make_pair((temp.first+1)%n,temp.second+1));

        }

    }

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

const int N = 100000+5;

using namespace std;

int vis[N];

int main() {

    int n;

    scanf("%d",&n);

    deque<pair<int,int> > Q;

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

    while(!Q.empty()){

        pair<int,int> temp=Q.front();

        Q.pop_front();

        if(!vis[temp.first]){

            vis[temp.first]=true;

            if(temp.first==0){

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

                break;

            }

            Q.push_front(make_pair((temp.first*10)%n,temp.second));

            Q.push_back(make_pair((temp.first+1)%n,temp.second+1));

        }

    }

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

const int N = 100000+5;

using namespace std;

int vis[N];

int main() {

    int n;

    scanf("%d",&n);

    deque<pair<int,int> > Q;

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

    while(!Q.empty()){

        pair<int,int> temp=Q.front();

        Q.pop_front();

        if(!vis[temp.first]){

            vis[temp.first]=true;

            if(temp.first==0){

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

                break;

            }

            Q.push_front(make_pair((temp.first*10)%n,temp.second));

            Q.push_back(make_pair((temp.first+1)%n,temp.second+1));

        }

    }

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

const int N = 100000+5;

using namespace std;

int vis[N];

int main() {

    int n;

    scanf("%d",&n);

    deque<pair<int,int> > Q;

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

    while(!Q.empty()){

        pair<int,int> temp=Q.front();

        Q.pop_front();

        if(!vis[temp.first]){

            vis[temp.first]=true;

            if(temp.first==0){

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

                break;

            }

            Q.push_front(make_pair((temp.first*10)%n,temp.second));

            Q.push_back(make_pair((temp.first+1)%n,temp.second+1));

        }

    }

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

const int N = 100000+5;

using namespace std;

int vis[N];

int main() {

    int n;

    scanf("%d",&n);

    deque<pair<int,int> > Q;

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

    while(!Q.empty()){

        pair<int,int> temp=Q.front();

        Q.pop_front();

        if(!vis[temp.first]){

            vis[temp.first]=true;

            if(temp.first==0){

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

                break;

            }

            Q.push_front(make_pair((temp.first*10)%n,temp.second));

            Q.push_back(make_pair((temp.first+1)%n,temp.second+1));

        }

    }

    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: 1.4850362237672579x):
#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;

}