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: 3.80912521627027x):
#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct node{

	int pre, to, val;

}edge[200010];

int head[100010], tot;

int k;

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

	edge[++tot] = node{head[u], v, l};

	head[u] = tot;

}

int dis[100010], vis[100010];

queue<int> q;

void spfa() {

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

	dis[1] = 1;

	vis[1] = 1;

	q.push(1);

	while (!q.empty()) {

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

		for (int i = head[x]; i; i = edge[i].pre) {

			int y = edge[i].to;

			if (dis[y] > dis[x] + edge[i].val) {

				dis[y] = dis[x] + edge[i].val;

				if (!vis[y]) {

					vis[y] = 1;

					q.push(y);

				}

			}

		}

		vis[x] = 0;

	}

}

int main() {

	cin >> k;

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

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

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

	}

	spfa();

	cout << dis[0];

	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.308619653275591x):
#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct node{

	int pre, to, val;

}edge[200010];

int head[100010], tot;

int k;

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

	edge[++tot] = node{head[u], v, l};

	head[u] = tot;

}

int dis[100010], vis[100010];

queue<int> q;

void spfa() {

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

	dis[1] = 1;

	vis[1] = 1;

	q.push(1);

	while (!q.empty()) {

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

		for (int i = head[x]; i; i = edge[i].pre) {

			int y = edge[i].to;

			if (dis[y] > dis[x] + edge[i].val) {

				dis[y] = dis[x] + edge[i].val;

				if (!vis[y]) {

					vis[y] = 1;

					q.push(y);

				}

			}

		}

		vis[x] = 0;

	}

}

int main() {

	cin >> k;

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

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

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

	}

	spfa();

	cout << dis[0];

	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.3323199044530671x):
#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct node{

	int pre, to, val;

}edge[200010];

int head[100010], tot;

int k;

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

	edge[++tot] = node{head[u], v, l};

	head[u] = tot;

}

int dis[100010], vis[100010];

queue<int> q;

void spfa() {

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

	dis[1] = 1;

	vis[1] = 1;

	q.push(1);

	while (!q.empty()) {

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

		for (int i = head[x]; i; i = edge[i].pre) {

			int y = edge[i].to;

			if (dis[y] > dis[x] + edge[i].val) {

				dis[y] = dis[x] + edge[i].val;

				if (!vis[y]) {

					vis[y] = 1;

					q.push(y);

				}

			}

		}

		vis[x] = 0;

	}

}

int main() {

	cin >> k;

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

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

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

	}

	spfa();

	cout << dis[0];

	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.846498542124344x):
#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct node{

	int pre, to, val;

}edge[200010];

int head[100010], tot;

int k;

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

	edge[++tot] = node{head[u], v, l};

	head[u] = tot;

}

int dis[100010], vis[100010];

queue<int> q;

void spfa() {

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

	dis[1] = 1;

	vis[1] = 1;

	q.push(1);

	while (!q.empty()) {

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

		for (int i = head[x]; i; i = edge[i].pre) {

			int y = edge[i].to;

			if (dis[y] > dis[x] + edge[i].val) {

				dis[y] = dis[x] + edge[i].val;

				if (!vis[y]) {

					vis[y] = 1;

					q.push(y);

				}

			}

		}

		vis[x] = 0;

	}

}

int main() {

	cin >> k;

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

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

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

	}

	spfa();

	cout << dis[0];

	return 0;

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

}


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

#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct node{

	int pre, to, val;

}edge[200010];

int head[100010], tot;

int k;

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

	edge[++tot] = node{head[u], v, l};

	head[u] = tot;

}

int dis[100010], vis[100010];

queue<int> q;

void spfa() {

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

	dis[1] = 1;

	vis[1] = 1;

	q.push(1);

	while (!q.empty()) {

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

		for (int i = head[x]; i; i = edge[i].pre) {

			int y = edge[i].to;

			if (dis[y] > dis[x] + edge[i].val) {

				dis[y] = dis[x] + edge[i].val;

				if (!vis[y]) {

					vis[y] = 1;

					q.push(y);

				}

			}

		}

		vis[x] = 0;

	}

}

int main() {

	cin >> k;

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

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

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

	}

	spfa();

	cout << dis[0];

	return 0;

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



using namespace std;



bool d[114514][46];

int M;

void f(int r, int s, int m)

{

	if (s > 45 || d[r][s])

		return;

	d[r][s] = true;

	if (!r && s && (!M || s < M))

		M = s;

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

		f((r * 10 + i) % m, s + i, m);

}



int main()

{

	int k;

	cin >> k;

	f(0, 0, k);

	cout << M << endl;

	return 0;

}


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

#include <deque>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	deque<int> q;

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

		d[i] = i == 1 ? 0 : 100;

	q.push_back(1);

	while (!q.empty()) {

		int u = q.front();

		q.pop_front();

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

			int v = (i ? u + 1 : u * 10) % k;

			int l = d[u] + i;

			if (d[v] <= l)

				continue;

			d[v] = l;

			i ? q.push_back(v) : q.push_front(v);

		}

	}

	cout << d[0] + 1 << endl;

	return 0;

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



using namespace std;



bool d[114514][46];

int M;

void f(int r, int s, int m)

{

	if (s > 45 || d[r][s])

		return;

	d[r][s] = true;

	if (!r && s && (!M || s < M))

		M = s;

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

		f((r * 10 + i) % m, s + i, m);

}



int main()

{

	int k;

	cin >> k;

	f(0, 0, k);

	cout << M << endl;

	return 0;

}


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

#include <deque>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	deque<int> q;

	q.push_back(1);

	while (q.front()) {

		int u = q.front();

		q.pop_front();

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			d[v] = d[u] + i;

			i ? q.push_back(v) : q.push_front(v);

		}

	}

	cout << *d << endl;

	return 0;

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

#include <set>



using namespace std;



const int L = 10;

struct dist {

	int s, N[L];

	dist() :s(100) {

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

			N[i] = !i;

	}

	dist(const dist &p, int i) :s(p.s + i) {

		//if (*p.N < 0) {

		//	*N = -1;

		//	return;

		//}

		//int k = i;

		//for (int j = 0; j < L; j++) {

		//	N[j] = i ? p.N[j] + k : p.N[j] * 10 + k;

		//	k = N[j] / 100000000;

		//	N[j] %= 100000000;

		//}

		//if (k) *N = -1;

	}

	bool operator<(const dist &d) const {

		if (s != d.s)

			return s < d.s;

		//if (*N < 0)

		//	return false;

		//else if (*d.N < 0)

		//	return true;

		//for (int i = L; i--;)

		//	if (N[i] != d.N[i])

		//		return N[i] < d.N[i];

		return false;

	}

} d[114514];



struct vert {

	int r;

	vert(int r) :r(r) {}

	bool operator<(const vert &v) const {

		if (d[r] < d[v.r])

			return true;

		if (d[v.r] < d[r])

			return false;

		return r < v.r;

	}

};



int main()

{

	int k;

	cin >> k;

	d[1].s = 1;

	set<vert> q;

	q.insert(1);

	while (!q.empty()) {

		int u = q.begin()->r;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			dist l(d[u], i);

			if (!(l < d[v]))

				continue;

			auto it = q.find(v);

			if (it != q.end())

				q.erase(it);

			d[v] = l;

			q.insert(v);

		}

	}

	cout << d->s << endl;

	//if (*d->N < 0) {

	//	cout << "inf" << endl;

	//	return 0;

	//}

	//for (int i = L; i--;) {

	//	if (!k) {

	//		cout.fill('0');

	//		cout.width(8);

	//		cout << right << d->N[i];

	//	}

	//	else if (d->N[i]) {

	//		k = 0;

	//		cout << d->N[i];

	//	}

	//}

	//cout << endl;

	return 0;

}


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

#include <deque>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	deque<int> q;

	q.push_back(1);

	while (q.front()) {

		int u = q.front();

		q.pop_front();

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			d[v] = d[u] + i;

			i ? q.push_back(v) : q.push_front(v);

		}

	}

	cout << *d << endl;

	return 0;

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



using namespace std;



bool d[114514][46];

int M;

void f(int r, int s, int m)

{

	if (s > 45 || d[r][s])

		return;

	d[r][s] = true;

	if (!r && s && (!M || s < M))

		M = s;

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

		f((r * 10 + i) % m, s + i, m);

}



int main()

{

	int k;

	cin >> k;

	f(0, 0, k);

	cout << M << endl;

	return 0;

}


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

#include <set>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	set<pair<int, int>> q;

	q.insert(make_pair(0, 111111));

	while (!q.empty()) {

		int u = q.begin()->second;

		q.erase(q.begin());

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

			if (u == 111111 && !i) {

				u = 0;

				continue;

			}

			int v = (u * 10 + i) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			auto it = q.find(make_pair(d[v], v));

			if (it != q.end())

				q.erase(it);

			d[v] = d[u] + i;

			q.insert(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

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

#include <set>



using namespace std;



const int L = 10;

struct dist {

	int s, N[L];

	dist() :s(100) {

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

			N[i] = !i;

	}

	dist(const dist &p, int i) :s(p.s + i) {

		//if (*p.N < 0) {

		//	*N = -1;

		//	return;

		//}

		//int k = i;

		//for (int j = 0; j < L; j++) {

		//	N[j] = i ? p.N[j] + k : p.N[j] * 10 + k;

		//	k = N[j] / 100000000;

		//	N[j] %= 100000000;

		//}

		//if (k) *N = -1;

	}

	bool operator<(const dist &d) const {

		if (s != d.s)

			return s < d.s;

		//if (*N < 0)

		//	return false;

		//else if (*d.N < 0)

		//	return true;

		//for (int i = L; i--;)

		//	if (N[i] != d.N[i])

		//		return N[i] < d.N[i];

		return false;

	}

} d[114514];



struct vert {

	int r;

	vert(int r) :r(r) {}

	bool operator<(const vert &v) const {

		if (d[r] < d[v.r])

			return true;

		if (d[v.r] < d[r])

			return false;

		return r < v.r;

	}

};



int main()

{

	int k;

	cin >> k;

	d[1].s = 1;

	set<vert> q;

	q.insert(1);

	while (!q.empty()) {

		int u = q.begin()->r;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			dist l(d[u], i);

			if (!(l < d[v]))

				continue;

			auto it = q.find(v);

			if (it != q.end())

				q.erase(it);

			d[v] = l;

			q.insert(v);

		}

	}

	cout << d->s << endl;

	//if (*d->N < 0) {

	//	cout << "inf" << endl;

	//	return 0;

	//}

	//for (int i = L; i--;) {

	//	if (!k) {

	//		cout.fill('0');

	//		cout.width(8);

	//		cout << right << d->N[i];

	//	}

	//	else if (d->N[i]) {

	//		k = 0;

	//		cout << d->N[i];

	//	}

	//}

	//cout << endl;

	return 0;

}


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

#include <set>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	set<pair<int, int>> q;

	q.insert(make_pair(0, 111111));

	while (!q.empty()) {

		int u = q.begin()->second;

		q.erase(q.begin());

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

			if (u == 111111 && !i) {

				u = 0;

				continue;

			}

			int v = (u * 10 + i) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			auto it = q.find(make_pair(d[v], v));

			if (it != q.end())

				q.erase(it);

			d[v] = d[u] + i;

			q.insert(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

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



using namespace std;



bool d[114514][46];

int M;

void f(int r, int s, int m)

{

	if (s > 45 || d[r][s])

		return;

	d[r][s] = true;

	if (!r && s && (!M || s < M))

		M = s;

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

		f((r * 10 + i) % m, s + i, m);

}



int main()

{

	int k;

	cin >> k;

	f(0, 0, k);

	cout << M << endl;

	return 0;

}


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

#include <set>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	set<pair<int, int>> q;

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

	while (q.begin()->second) {

		int u = q.begin()->second;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			d[v] = d[u] + i;

			q.insert(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

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

#include <set>



using namespace std;



const int L = 10;

struct dist {

	int s, N[L];

	dist() :s(100) {

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

			N[i] = !i;

	}

	dist(const dist &p, int i) :s(p.s + i) {

		//if (*p.N < 0) {

		//	*N = -1;

		//	return;

		//}

		//int k = i;

		//for (int j = 0; j < L; j++) {

		//	N[j] = i ? p.N[j] + k : p.N[j] * 10 + k;

		//	k = N[j] / 100000000;

		//	N[j] %= 100000000;

		//}

		//if (k) *N = -1;

	}

	bool operator<(const dist &d) const {

		if (s != d.s)

			return s < d.s;

		//if (*N < 0)

		//	return false;

		//else if (*d.N < 0)

		//	return true;

		//for (int i = L; i--;)

		//	if (N[i] != d.N[i])

		//		return N[i] < d.N[i];

		return false;

	}

} d[114514];



struct vert {

	int r;

	vert(int r) :r(r) {}

	bool operator<(const vert &v) const {

		if (d[r] < d[v.r])

			return true;

		if (d[v.r] < d[r])

			return false;

		return r < v.r;

	}

};



int main()

{

	int k;

	cin >> k;

	d[1].s = 1;

	set<vert> q;

	q.insert(1);

	while (!q.empty()) {

		int u = q.begin()->r;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			dist l(d[u], i);

			if (!(l < d[v]))

				continue;

			auto it = q.find(v);

			if (it != q.end())

				q.erase(it);

			d[v] = l;

			q.insert(v);

		}

	}

	cout << d->s << endl;

	//if (*d->N < 0) {

	//	cout << "inf" << endl;

	//	return 0;

	//}

	//for (int i = L; i--;) {

	//	if (!k) {

	//		cout.fill('0');

	//		cout.width(8);

	//		cout << right << d->N[i];

	//	}

	//	else if (d->N[i]) {

	//		k = 0;

	//		cout << d->N[i];

	//	}

	//}

	//cout << endl;

	return 0;

}


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

#include <set>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	set<pair<int, int>> q;

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

	while (q.begin()->second) {

		int u = q.begin()->second;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			d[v] = d[u] + i;

			q.insert(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

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



using namespace std;



bool d[114514][46];

int M;

void f(int r, int s, int m)

{

	if (s > 45 || d[r][s])

		return;

	d[r][s] = true;

	if (!r && s && (!M || s < M))

		M = s;

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

		f((r * 10 + i) % m, s + i, m);

}



int main()

{

	int k;

	cin >> k;

	f(0, 0, k);

	cout << M << endl;

	return 0;

}


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

#include <set>



using namespace std;



int d[114514];



int main()

{

	int k;

	cin >> k;

	d[1] = 1;

	set<pair<int, int>> q;

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

	while (q.begin()->second) {

		int u = q.begin()->second;

		q.erase(q.begin());

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

			int v = (i ? u + 1 : u * 10) % k;

			if (d[v] && d[v] <= d[u] + i)

				continue;

			auto it = q.find(make_pair(d[v], v));

			if (it != q.end())

				q.erase(it);

			d[v] = d[u] + i;

			q.insert(make_pair(d[v], v));

		}

	}

	cout << *d << endl;

	return 0;

}