stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
/*

 * 很神奇的一道题目

 * 求出k的倍数的正数x，使得x的位数和最小。

 * eg k = 6 x = 12(位数和为3) x = 30(位数和为3)

 * 

 * 考虑正数x 其变为 x+1 需要代价1.

 *    正数x 变成 x*10 需要代价0.

 * 由于我们只需要得到k的倍数，也就是说在 %k 意义下为0的点。

 * 所以只有[0,k-1]k点。对每个点建立两条边，分别为(x+1)%k 和 (x*10)%k

 */

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

const int inf = 0x3f3f3f3f;

struct Edge {

    int to,val;

    Edge(){}

    Edge(int _t,int _v){to = _t;val = _v;}

};

struct qNode {

    int u,val;

    qNode(){}

    qNode(int _u,int _v) {u = _u;val = _v;}

    bool operator < (const qNode &a) const{

        return val > a.val;

    }

};

vector<Edge> ways[maxn];

int dist[maxn];

bool vis[maxn];

int n;

inline void init() {

    for(int i=0;i<maxn;i++) ways[i].clear();

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

    memset(dist,inf,sizeof(dist));

}

inline void addedge(int from,int to,int val) {

    ways[from].push_back(Edge(to,val));

}

int solve(int from,int to) {

    priority_queue<qNode> qu;

    dist[from] = 1;

    qu.push(qNode(from,1));

    qNode now;

    while(!qu.empty()) {

        now = qu.top();qu.pop();

        int u = now.u;

        if(vis[u]) continue;

        vis[u] = true;

        for(auto tmp:ways[u]) {

            int v = tmp.to,cost = tmp.val;

            if(!vis[v] && dist[v] > dist[u]+cost) {

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

                qu.push(qNode(v,dist[v]));

            }

        }

    }

    return dist[to];

}

int main()

{

    while(~scanf("%d",&n)){

        init();

        for(int i=1;i<n;i++) {

            addedge(i,(i+1)%n,1);

            addedge(i,(i*10)%n,0);

        }

        int ans = solve(1,0);

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

    }

    return 0;

}

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

using namespace std;



#define int long long

#define pii pair<int,int> 



int K;

int dist[100010];

bool inh[100010];



main()

{

	ios::sync_with_stdio(false);

	

	cin>>K;

	

	int ans=1000000010;

	

	memset(dist,-1,sizeof(dist));

	priority_queue<pii> H;

	dist[1]=1;

	H.push({-1,1});

	inh[1]=true;

	

	while(!H.empty())

	{

		int u=H.top().second; H.pop();

		if(!inh[u]) continue;

		inh[u]=false; // cout<<u<<endl;

		if(u%K==0) ans=min(ans,dist[u]);

		int v=u*10%K;

		if(dist[v]==-1 || dist[v]>dist[u])

		{

			dist[v]=dist[u];

			H.push({-dist[v],v});

			inh[v]=true;

		}

		v=(u+1)%K;

		if(dist[v]==-1 || dist[v]>dist[u]+1)

		{

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

			H.push({-dist[v],v});

			inh[v]=true;

		}

	}

	cout<<ans<<endl;

	

	return 0;

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

using namespace std;



const int MAX_N=1e5+10;

const int INF=1e9+10;



int K,N,M,dist[MAX_N];

vector <pair<int,int> > g[MAX_N];

priority_queue <pair<int,int> > Q;



void get_dijk(){

	for(int i=0;i<MAX_N;i++) dist[i]=INF;

	dist[1]=1;

	Q.push(make_pair(-dist[1],1));

	while(Q.size()){

		int val=-Q.top().first,x=Q.top().second;

		Q.pop();

		if(dist[x]<val) continue;

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

			int cost=g[x][i].first,to=g[x][i].second;

			if(dist[to]>cost+dist[x]){

				dist[to]=cost+dist[x];

				Q.push(make_pair(-dist[to],to));

			}

		}

	}

}



int main(){

	cin>>K;

	for(int i=1;i<K;i++){

		g[i].push_back(make_pair(0,i*10%K));

		g[i].push_back(make_pair(1,(i+1)%K));

	}

	get_dijk();

	cout<<dist[0]<<endl;

	return 0;

}

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

using namespace std;



#define int long long

#define pii pair<int,int> 



int K;

int dist[100010];

bool inh[100010];



main()

{

	ios::sync_with_stdio(false);

	

	cin>>K;

	

	int ans=1000000010;

	

	memset(dist,-1,sizeof(dist));

	priority_queue<pii> H;

	dist[1]=1;

	H.push({-1,1});

	inh[1]=true;

	

	while(!H.empty())

	{

		int u=H.top().second; H.pop();

		if(!inh[u]) continue;

		inh[u]=false; // cout<<u<<endl;

		if(u%K==0) ans=min(ans,dist[u]);

		int v=u*10%K;

		if(dist[v]==-1 || dist[v]>dist[u])

		{

			dist[v]=dist[u];

			H.push({-dist[v],v});

			inh[v]=true;

		}

		v=(u+1)%K;

		if(dist[v]==-1 || dist[v]>dist[u]+1)

		{

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

			H.push({-dist[v],v});

			inh[v]=true;

		}

	}

	cout<<ans<<endl;

	

	return 0;

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

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

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

#include <fstream>

#include <cstdio>

#include <cassert>

#include <complex>

#include <cmath>

#include <algorithm>

#include <vector>

#include <string>

#include <cstdlib>

#include <cstring>

#include <iomanip>

#include <numeric>

#include <sstream>

#include <ctime>

#include <cctype>

#include <set>

#include <map>

#include <queue>

#include <bitset>

#include <deque>

#include <stack>

#include <memory.h>

using namespace std;

#define ll long long 

#define mp make_pair

deque<pair<int,int> > q;

bool vis[100005];

int k,ans=0; 

int main()

{

	cin>>k;

	q.push_front(mp(1,1));

	while(!q.empty()){

		pair<int,int> x=q.front();

		q.pop_front();

		if(x.first==0){

			cout<<ans+x.second;

			return 0;

		}

		if(vis[x.first]){

			continue;

		}

		vis[x.first]=1;

		q.push_back(mp((x.first+1)%k,x.second+1));

		q.push_front(mp((x.first*10%k),x.second));

	}

    return 0;

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

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

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

#include<deque>

using namespace std;

int k,dist[100000];

deque<int> q;

int main(){

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin>>k;

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

	{

		dist[i]=1000000009;

	}

	dist[1]=1;

	q.push_back(1);

	while(q.size())

	{

		int x=q.front();

		q.pop_front();

		if(dist[(10*x)%k]>dist[x])

		{

			dist[(10*x)%k]=dist[x];

			q.push_front((10*x)%k);

		}

		if(dist[(x+1)%k]>dist[x]+1)

		{

			dist[(x+1)%k]=dist[x]+1;

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

		 } 

	}

	cout<<dist[0];

	return 0;

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

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

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

#include <queue>

#define mp make_pair

using namespace std;

deque<pair<int,int> > q;bool vis[100005];int k,ans=0; 

int main(){

	cin>>k;q.push_front(mp(1,1));while(!q.empty()){pair<int,int> x=q.front();q.pop_front();if(x.first==0){cout<<ans+x.second;return 0;}if(vis[x.first]){continue;}vis[x.first]=1;q.push_back(mp((x.first+1)%k,x.second+1));q.push_front(mp((x.first*10%k),x.second));}return 0;

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

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

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

#include <ostream>

#include <istream>

#include <cmath>

#include <string>

#include <vector>

#include <sstream>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <vector>

#include <set>

#define pb push_back

#define ppb pop_back

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

#define for1(i, n) for (int i = 1; i <= int(n); i++)

#define forv(i, v) forn(i, v.size())

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

#define pb push_back

#define mp make_pair

#define CIN_FILE "input.txt"

#define COUT_FILE "output.txt"

#define pi 3.1415926535897932

#define NMAX 100005

#define INF 1000000007

typedef pair<int, int> pii;

typedef long long ll;

typedef long double ld;

int K,dist[100000];

deque<int> todo;

int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin>>K;

	for(int i=0; i<K; i++)dist[i]=INF;

	dist[1]=1;

	todo.pb(1);

	while(todo.size()) {

		int x=todo.front();

		todo.pop_front();

		if(dist[(10*x)%K]>dist[x]) {

			dist[(10*x)%K]=dist[x];

			todo.push_front((10*x)%K) ;

		}

		if(dist[(x+1)%K]>dist[x]+1) {

			dist[(x+1)%K]=dist[x]+1;

			todo.push_back((x+1)%K);

		}

	}

	cout<<dist[0];

	return 0;

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

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.0296130970033226x):
// i will show you da wae

#include <bits/stdc++.h>

#define mp make_pair

#define pb push_back

#define fill(x,v) memset(x,v,sizeof(x))

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

#define trace(x) cout << #x << " = " << x << endl

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

#define N 100050

using namespace std;

typedef long long ll;

typedef pair<int,int> ii;



ll dp[N];



ll solve(int k){

    priority_queue<ii,vector<ii>,greater<ii> > pq;

    FOR(i,0,k) dp[i] = LLONG_MAX;

    FOR(i,1,10){

        pq.push(ii(i,i%k));

        dp[i%k] = i;

    }



    while(1){

        ii top = pq.top();

        pq.pop();

        ll sum = top.first, mod = top.second;

        if(mod == 0) return sum;

        FOR(i,0,10){

            ll nmod = (mod*10+i)%k, nsum = sum + i;

            if(dp[nmod] > nsum){

                dp[nmod] = nsum;

                pq.push(ii(nsum,nmod));

            }

        }

    }

    return 0;

}



int main(){

    

    int k;

    cin >> k;

    cout << solve(k) << endl;



    return 0;

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

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

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

#include<cstdio>

using namespace std;

typedef pair<int,int> P;

int d[101000];P q[201000];int H=100000,T=100000;

int h[101000],nxt[201000],K=0,to[201000],cost[201000];

void ins(int u,int v,int c){nxt[++K]=h[u];h[u]=K;to[K]=v;cost[K]=c;}

int main()

{

	int k;scanf("%d",&k);

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

	q[T++]=P(1,1);

	while(H<T)

	{

		P p=q[H++];int u=p.first;if(d[u])continue;d[u]=p.second;

		for(int i=h[u];i;i=nxt[i])if(!cost[i])q[--H]=P(to[i],d[u]);else q[T++]=P(to[i],d[u]+1);

	}

	printf("%d",d[0]);return 0;

}

//我们发现，在模k意义下同余的sum是等价的，只要保留答案最小的即可

//新建一个图，共 k 个节点，代表 模k 得到的值。

//建边的依据是已知一个数x%k=p，那么在 x 后面再加一位数得到 y ，可以知道 y%k 的值，于是就得到了一个图，每条边代表往后加一位，边权就是这一位的数字。

//跑一遍最短路，其中 d[i] 意义就是模 k 余 i 的数中每一位的和最少是多少，开始 1~9 都加入队列

//但是还可以优化

//我们是把a向(a*10+b)%k连一条边权为b的边

//画个图我们会发现，只要把a向a*10%k 连一条边权为0的边 和 (a+1)%k 连一条边权为1的边即可，这与原图是等价的

//这种连边可以理解为把这个数后面加一个0或者把这个数加1 

//跑01bfs即可
// Slower C++ solution:
#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int e[100009],k;

typedef pair<int,int> P;

deque<P>q;

int main(){scanf("%d",&k);

    memset(e,0,sizeof(e));q.push_back(make_pair(1,1));

    while(!q.empty()){P x=q.front();q.pop_front();

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

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

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

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

    }return 0;

}

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

#include<cstdio>

using namespace std;

typedef pair<int,int> P;

int d[101000];P q[201000];int H=100000,T=100000;

int h[101000],nxt[201000],K=0,to[201000],cost[201000];

void ins(int u,int v,int c){nxt[++K]=h[u];h[u]=K;to[K]=v;cost[K]=c;}

int main()

{

	int k;scanf("%d",&k);

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

	q[T++]=P(1,1);

	while(H<T)

	{

		P p=q[H++];int u=p.first;if(d[u])continue;d[u]=p.second;

		for(int i=h[u];i;i=nxt[i])if(!cost[i])q[--H]=P(to[i],d[u]);else q[T++]=P(to[i],d[u]+1);

	}

	printf("%d",d[0]);return 0;

}

//我们发现，在模k意义下同余的sum是等价的，只要保留答案最小的即可

//新建一个图，共 k 个节点，代表 模k 得到的值。

//建边的依据是已知一个数x%k=p，那么在 x 后面再加一位数得到 y ，可以知道 y%k 的值，于是就得到了一个图，每条边代表往后加一位，边权就是这一位的数字。

//跑一遍最短路，其中 d[i] 意义就是模 k 余 i 的数中每一位的和最少是多少，开始 1~9 都加入队列

//但是还可以优化

//我们是把a向(a*10+b)%k连一条边权为b的边

//画个图我们会发现，只要把a向a*10%k 连一条边权为0的边 和 (a+1)%k 连一条边权为1的边即可，这与原图是等价的

//这种连边可以理解为把这个数后面加一个0或者把这个数加1 

//跑01bfs即可
// Slower C++ solution:
#include <queue>

#include <stdio.h>

#include <string.h>

#define R register

#define MN 100005

std::deque<int> q;

int k,dis[MN];bool vis[MN];

int main(){

	scanf("%d",&k);

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

	dis[1]=0;q.push_back(1);

	while(!q.empty()){

		R int x=q.front();q.pop_front();

		if (vis[x]) continue;

		if (!x) break;vis[x]=1;

		if (dis[x*10%k]>dis[x]){

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

			q.push_front(x*10%k);

		}

		if (dis[x+1==k?0:x+1]>dis[x]+1){

			q.push_back(x+1==k?0:x+1);

			dis[x+1==k?0:x+1]=dis[x]+1;

		}

	}printf("%d\n",dis[0]+1);return 0;

}

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

#include<cstdio>

using namespace std;

typedef pair<int,int> P;

int d[101000];P q[201000];int H=100000,T=100000;

int h[101000],nxt[201000],K=0,to[201000],cost[201000];

void ins(int u,int v,int c){nxt[++K]=h[u];h[u]=K;to[K]=v;cost[K]=c;}

int main()

{

	int k;scanf("%d",&k);

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

	q[T++]=P(1,1);

	while(H<T)

	{

		P p=q[H++];int u=p.first;if(d[u])continue;d[u]=p.second;

		for(int i=h[u];i;i=nxt[i])if(!cost[i])q[--H]=P(to[i],d[u]);else q[T++]=P(to[i],d[u]+1);

	}

	printf("%d",d[0]);return 0;

}

//我们发现，在模k意义下同余的sum是等价的，只要保留答案最小的即可

//新建一个图，共 k 个节点，代表 模k 得到的值。

//建边的依据是已知一个数x%k=p，那么在 x 后面再加一位数得到 y ，可以知道 y%k 的值，于是就得到了一个图，每条边代表往后加一位，边权就是这一位的数字。

//跑一遍最短路，其中 d[i] 意义就是模 k 余 i 的数中每一位的和最少是多少，开始 1~9 都加入队列

//但是还可以优化

//我们是把a向(a*10+b)%k连一条边权为b的边

//画个图我们会发现，只要把a向a*10%k 连一条边权为0的边 和 (a+1)%k 连一条边权为1的边即可，这与原图是等价的

//这种连边可以理解为把这个数后面加一个0或者把这个数加1 

//跑01bfs即可
// Slower C++ solution:
#include <stdio.h>

#include <string.h>

#include <queue>

#define N 100010

int n,d[N];char inq[N];

inline int spfa(int s,int t) {

	std::queue<int> q;int u,v;

	memset(d,33,sizeof(d));

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

	while(!q.empty()) {

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

		v=u*10%n;

		if(d[u]<d[v]) {

			d[v]=d[u];

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

		}

		v=u+1;if(v==n) v=0;

		if(d[u]+1<d[v]) {

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

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

		}

	}

	return d[t];

}

int main() {

	scanf("%d",&n);

	printf("%d\n",1+spfa(1,0));

	return 0;

}

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

#include<cstdio>

using namespace std;

typedef pair<int,int> P;

int d[101000];P q[201000];int H=100000,T=100000;

int h[101000],nxt[201000],K=0,to[201000],cost[201000];

void ins(int u,int v,int c){nxt[++K]=h[u];h[u]=K;to[K]=v;cost[K]=c;}

int main()

{

	int k;scanf("%d",&k);

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

	q[T++]=P(1,1);

	while(H<T)

	{

		P p=q[H++];int u=p.first;if(d[u])continue;d[u]=p.second;

		for(int i=h[u];i;i=nxt[i])if(!cost[i])q[--H]=P(to[i],d[u]);else q[T++]=P(to[i],d[u]+1);

	}

	printf("%d",d[0]);return 0;

}

//我们发现，在模k意义下同余的sum是等价的，只要保留答案最小的即可

//新建一个图，共 k 个节点，代表 模k 得到的值。

//建边的依据是已知一个数x%k=p，那么在 x 后面再加一位数得到 y ，可以知道 y%k 的值，于是就得到了一个图，每条边代表往后加一位，边权就是这一位的数字。

//跑一遍最短路，其中 d[i] 意义就是模 k 余 i 的数中每一位的和最少是多少，开始 1~9 都加入队列

//但是还可以优化

//我们是把a向(a*10+b)%k连一条边权为b的边

//画个图我们会发现，只要把a向a*10%k 连一条边权为0的边 和 (a+1)%k 连一条边权为1的边即可，这与原图是等价的

//这种连边可以理解为把这个数后面加一个0或者把这个数加1 

//跑01bfs即可
// Slower C++ solution:
#include <iostream>

#include <queue>

using namespace std;



int k,dist[100010];

bool used[100010];

deque<int> q;



inline void add_front(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_front(x);

	}

}



inline void add_back(int x,int d)

{

	if(d<dist[x])

	{

		dist[x]=d;

		q.push_back(x);

	}

}



int main()

{

	cin>>k;

	fill(dist,dist+100000,(1e9+7));

	

	add_front(1,0);

	while(!q.empty())

	{

		int x=q[0];q.pop_front();

		

		if(used[x]) continue;

		used[x]=1;

		

		int d=dist[x],cx=x*10%k;

		add_front(cx,d);

		

		cx=(x+1)%k;

		add_back(cx,d+1);

	}

	

	cout<<dist[0]+1;

	

	return 0;

}

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

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<int,int> P;

const int maxn=2e5+100;

int k;

bool vis[maxn];

 

int main()

{

    //freopen("1.txt","r",stdin);

    while (scanf("%d",&k)!=EOF)

    {

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

        deque<P> q;

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

        while (!q.empty())

        {

            auto t=q.front(); q.pop_front();

            if (vis[t.first]) continue;

            vis[t.first]=1;

            if (t.first==0)

            {

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

                break;

            }

            q.push_front(make_pair(t.first*10%k,t.second));

            q.push_back(make_pair((t.first+1)%k,t.second+1));

        }

    }

    return 0;

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

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

int e[100009],k;

typedef pair<int,int> P;

deque<P>q;

int main(){scanf("%d",&k);

    memset(e,0,sizeof(e));q.push_back(make_pair(1,1));

    while(!q.empty()){P x=q.front();q.pop_front();

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

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

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

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

    }return 0;

}

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

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<int,int> P;

const int maxn=2e5+100;

int k;

bool vis[maxn];

 

int main()

{

    //freopen("1.txt","r",stdin);

    while (scanf("%d",&k)!=EOF)

    {

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

        deque<P> q;

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

        while (!q.empty())

        {

            auto t=q.front(); q.pop_front();

            if (vis[t.first]) continue;

            vis[t.first]=1;

            if (t.first==0)

            {

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

                break;

            }

            q.push_front(make_pair(t.first*10%k,t.second));

            q.push_back(make_pair((t.first+1)%k,t.second+1));

        }

    }

    return 0;

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

#include <stdio.h>

#include <string.h>

#define R register

#define MN 100005

std::deque<int> q;

int k,dis[MN];bool vis[MN];

int main(){

	scanf("%d",&k);

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

	dis[1]=0;q.push_back(1);

	while(!q.empty()){

		R int x=q.front();q.pop_front();

		if (vis[x]) continue;

		if (!x) break;vis[x]=1;

		if (dis[x*10%k]>dis[x]){

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

			q.push_front(x*10%k);

		}

		if (dis[x+1==k?0:x+1]>dis[x]+1){

			q.push_back(x+1==k?0:x+1);

			dis[x+1==k?0:x+1]=dis[x]+1;

		}

	}printf("%d\n",dis[0]+1);return 0;

}

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

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

typedef pair<int,int> P;

const int maxn=2e5+100;

int k;

bool vis[maxn];

 

int main()

{

    //freopen("1.txt","r",stdin);

    while (scanf("%d",&k)!=EOF)

    {

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

        deque<P> q;

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

        while (!q.empty())

        {

            auto t=q.front(); q.pop_front();

            if (vis[t.first]) continue;

            vis[t.first]=1;

            if (t.first==0)

            {

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

                break;

            }

            q.push_front(make_pair(t.first*10%k,t.second));

            q.push_back(make_pair((t.first+1)%k,t.second+1));

        }

    }

    return 0;

}