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

using namespace std;

#define fi first

#define se second

typedef pair<int,int> pi;

pi u;

deque<pi>q;

int k;

bool vis[100002];

int main(){

	scanf("%d",&k);

	q.push_front({1,1});

	while (1){

		u=q.front(),q.pop_front();

		if (vis[u.fi]) continue;

		vis[u.fi]=1;

		if (!u.fi) return printf("%d",u.se),0;

		q.push_front({u.fi*10%k,u.se});

		q.push_back({(u.fi+1)%k,u.se+1});

	}

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

using namespace std;

#define fi first

#define se second

typedef pair<int,int> pi;

pi u;

deque<pi>q;

int k;

bool vis[100002];

int main(){

	scanf("%d",&k);

	q.push_front({1,1});

	while (1){

		u=q.front(),q.pop_front();

		if (vis[u.fi]) continue;

		vis[u.fi]=1;

		if (!u.fi) return printf("%d",u.se),0;

		q.push_front({u.fi*10%k,u.se});

		q.push_back({(u.fi+1)%k,u.se+1});

	}

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

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

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

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

}
// 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.2098816860713x):
#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<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.8294103742934495x):
#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;

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

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

}