stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5;



int n,len,ans = INF;

int head[MAXN],in[MAXN],dis[MAXN];



struct Edge{

	int to,next,w;

} e[MAXN * 20];



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

	e[++len].to = v;

	e[len].next = head[u];

	e[len].w = w;

	head[u] = len;

}



void spfa(int s){

	queue<int> q;

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

	memset(in,0,sizeof(in));

	q.push(s);

	dis[s] = s;

	while(!q.empty()){

		int u = q.front();

		q.pop();

		in[u] = 0;

		for(int i = head[u];i != -1;i = e[i].next){

			int v = e[i].to;

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

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

				if(!in[v]){

					in[v] = 1;

					q.push(v);

				}

			}

		}

	}

}



int main(){

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

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

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

	scanf("%d",&n);

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

		for(int j = 0;j <= 9;j++)

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

	}

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

		spfa(i);

		ans = min(ans,dis[0]);

	}

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

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#include <cstring>

#include <vector>

#include <algorithm>

#include <cstdio>

#include <iostream>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;



const int INF = 0x3f3f3f3f;

const int MAXN = 1e5 + 5;



int n,len;

int head[MAXN],in[MAXN];

deque<pii> q;



int main(){

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

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

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

	scanf("%d",&n);

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

	while(!q.empty()){

		pii u = q.front();

		q.pop_front();

		if(in[u.first])

		    continue;

		if(u.first == 0){

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

			return 0;

		}

		in[u.first] = 1;

		q.push_front(make_pair((u.first * 10) % n,u.second));

		q.push_back(make_pair((u.first + 1) % n,u.second + 1));

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;

using pii = pair<int, int>;



template <class T>

struct edge {

  int from, to; T cost;

  edge() {}

  edge(int f, int t, T c): from(f), to(t), cost(c) {}

};



vector<edge<int>> G[100010];

int dis[100010];



int main() {

  cin.tie(0);

  ios_base::sync_with_stdio(false);

  cout << fixed << setprecision(10);



  int K;

  cin >> K;



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

    G[i].emplace_back(i, (i + 1) % K, 1);

    if (i) G[i].emplace_back(i, i * 10 % K, 0);

  }



  fill(dis, dis + K, 1 << 30);

  dis[1] = 1;

  deque<int> deq = {1};

  while (!deq.empty()) {

    int v = deq.front(); deq.pop_front();

    for (auto e : G[v]) {

      if (dis[e.to] > dis[v] + e.cost) {

        dis[e.to] = dis[v] + e.cost;

        if (e.cost) deq.emplace_front(e.to);

        else deq.emplace_back(e.to);

      }

    }

  }

  cout << dis[0] << endl;



  return 0;

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>



using namespace std;

using ll = long long;

using pii = pair<int, int>;



template <class T>

struct Dijkstra {

  struct edge {

    int from, to; T cost;

    edge() {}

    edge(int f, int t, T c) : from(f), to(t), cost(c) {}

  };



  int N;

  vector<vector<edge>> G;

  vector<T> dis;

  vector<int> prev;

  Dijkstra() {}

  Dijkstra(int N) : N(N), G(N), dis(N), prev(N, -1) {}

  void add_edge(int f, int t, T c) {

    G[f].emplace_back(f, t, c);

  }

  void shortest_path(int s, T INF) {

    fill(dis.begin(), dis.end(), INF);

    dis[s] = 0;

    using P = pair<T, int>;

    priority_queue<P, vector<P>, greater<P>> que;

    que.emplace(0, s);

    while (!que.empty()) {

      P p = que.top(); que.pop();

      int v = p.second;

      if (dis[v] < p.first) continue;

      for (auto &e : G[v]) {

        if (dis[e.to] > dis[v] + e.cost) {

          dis[e.to] = dis[v] + e.cost;

          prev[e.to] = v;

          que.emplace(dis[e.to], e.to);

        }

      }

    }

  }

  vector<int> get_path(int t) {

    vector<int> path;

    for(; t != -1; t = prev[t]) path.push_back(t);

    reverse(path.begin(), path.end());

    return path;

  }

};



int main() {

  cin.tie(0);

  ios_base::sync_with_stdio(false);

  cout << fixed << setprecision(10);



  int K;

  cin >> K;

  Dijkstra<int> D(K);

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

    D.add_edge(i, (i + 1) % K, 1);

    if (i) D.add_edge(i, i * 10 % K, 0);

  }

  D.shortest_path(1, 1 << 30);

  cout << D.dis[0] + 1 << endl;



  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

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;

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

{

    G[cnt].to=v;

    G[cnt].w=w;

    G[cnt].from=head[u];

    head[u]=cnt++;

}

void spfa(int s)

{

    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(int 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()

{

    int k;

    scanf("%d", &k);

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

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

    cnt=0;

    for(int 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;

}




// Optimized solution to the same problem (faster):
#include<iostream>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 100005;

const LL inf = 0x3f3f3f3f;

int main(void){

    int k,v,u;

    cin>>k;

    vector<int> dp(k,46);

    dp[1] = 1;

    queue<int> deq;

    deq.push(1);

    while(!deq.empty()){

        v=deq.front();

        deq.pop();

        u = (v*10)%k;

        if(dp[u] > dp[v]){

            dp[u] = dp[v];

            deq.push(u);

        }

        u = (v+1)%k;

        if(dp[u] > dp[v]+1){

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

            deq.push(u);

        }

    }

    cout<<dp[0]<<endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <queue>

#include <string.h>

using namespace std;



int k;

deque<pair<int,int> > q;

bool used[100010];



int main()

{

	cin>>k;

	

	q.push_back({1,1});

	while(!q.empty())

	{

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

		if(!x.first) {cout<<x.second;return 0;}

		

		if(!used[x.first])

		{

			used[x.first]=1;

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

			q.push_back({x.first+1,x.second+1});

		}

	}

	

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<queue>

#include<algorithm>

#include<map>

#include<set>

#include<vector>

#include<math.h>

#include<time.h>



using namespace std;



#define INF 1000000007

#define LINF (1LL << 62)



typedef long long i64;

typedef pair<i64,i64> P;





int n;

int dp[101010];



int main(){

	cin >> n;

	

	for(int i = 0; i < 101010; i++) dp[i] = INF;

	deque<P> q;

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

	while(!q.empty()){

		P p = q.front();

		q.pop_front();

		i64 sc = p.first, now = p.second;

		if(dp[now] <= sc) continue;

		dp[now] = sc;

		if(now == 0) break;

		int nx = (now+1)%n;

		q.push_back(P(sc+1, nx));

		nx = (now*10)%n;

		q.push_front(P(sc, nx));

	}

	

	cout << dp[0] << endl;

	

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>



using namespace std;



#define INF 1000000007

#define LINF (1LL << 60)

#define PI 3.14159265358979



typedef long long i64;

typedef pair<i64,i64> P;



inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }







int n;

bool dp[101010];

void solve(){

	cin >> n;

	

	priority_queue<P,vector<P>,greater<P>> q;

	q.push({1,1});

	while(!q.empty()){

		P p = q.top(); q.pop();

		int c = p.first, a = p.second;

		a %= n;

		if(a == 0){

			cout << c << endl;

			break;

		}

		if(dp[a]) continue;

		dp[a] = 1;

		q.push({c,a*10});

		q.push({c+1,a+1});

		//cout << c << " " << a << endl;

	}

}



int main(){

	std::cin.tie(0);

	std::ios::sync_with_stdio(false);

	int t = 1;

	//cin >> t;

	while(t--){

		solve();

	}

	

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;



#define INF 1000000007

#define LINF (1LL << 60)

#define PI 3.14159265358979



typedef long long i64;

typedef pair<i64,i64> P;



inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }







int n;

int dp[101010];

void solve(){

	cin >> n;

	

	fill(dp,dp+101010, INF);

	priority_queue<P,vector<P>,greater<P>> q;

	q.push({1,1});

	while(!q.empty()){

		P p = q.top(); q.pop();

		int c = p.first, a = p.second;

		a %= n;

		if(a == 0){

			cout << c << endl;

			break;

		}

		if(dp[a] <= c) continue;

		dp[a] = c;

		q.push({c,a*10});

		q.push({c+1,a+1});

		//cout << c << " " << a << endl;

	}

}



int main(){

	std::cin.tie(0);

	std::ios::sync_with_stdio(false);

	int t = 1;

	//cin >> t;

	while(t--){

		solve();

	}

	

	return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>



using namespace std;



#define INF 1000000007

#define LINF (1LL << 60)

#define PI 3.14159265358979



typedef long long i64;

typedef pair<i64,i64> P;



inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }



template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }







int n;

bool dp[101010];

void solve(){

	cin >> n;

	

	priority_queue<P,vector<P>,greater<P>> q;

	q.push({1,1});

	while(!q.empty()){

		P p = q.top(); q.pop();

		int c = p.first, a = p.second;

		a %= n;

		if(a == 0){

			cout << c << endl;

			break;

		}

		if(dp[a]) continue;

		dp[a] = 1;

		q.push({c,a*10});

		q.push({c+1,a+1});

		//cout << c << " " << a << endl;

	}

}



int main(){

	std::cin.tie(0);

	std::ios::sync_with_stdio(false);

	int t = 1;

	//cin >> t;

	while(t--){

		solve();

	}

	

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
//problem:T99402

#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define mk make_pair

#define lob lower_bound

#define upb upper_bound

#define fst first

#define scd second



typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;



inline int read(){

	int f=1,x=0;char ch=getchar();

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

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

	return x*f;

}

inline ll readll(){

	ll f=1,x=0;char ch=getchar();

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

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

	return x*f;

}



const int MAXN=1e5+5;

ll dis[MAXN];

struct EDGE{int nxt,to,w;}edge[MAXN*10+100];

int n,head[MAXN],tot;

inline void add_edge(int u,int v,int w){edge[++tot].nxt=head[u];edge[tot].to=v;edge[tot].w=w;head[u]=tot;}

struct RULE{bool operator()(int &x,int &y)const{return dis[x]>dis[y];}};

int main() {

	n=read();if(n==1){puts("1");return 0;}

	for(int i=0;i<n;++i)for(int j=0;j<10;++j)add_edge(i,(i*10+j)%n,j);

	for(int i=1;i<10;++i)add_edge(n,i,i);

	memset(dis,0x3f,sizeof(dis));dis[n]=0;priority_queue<int,vector<int>,RULE>q;q.push(n);

	while(!q.empty()){

		int u=q.top();q.pop();

		//if(u==0){cout<<dis[u]<<endl;return 0;}

		for(int i=head[u];i;i=edge[i].nxt){

			int v=edge[i].to;

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

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

				q.push(v);

			}

		}

	}cout<<dis[0]<<endl;return 0;

}

// Optimized solution to the same problem (faster):
//problem:T99402

#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define mk make_pair

#define lob lower_bound

#define upb upper_bound

#define fst first

#define scd second



typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;



inline int read(){

	int f=1,x=0;char ch=getchar();

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

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

	return x*f;

}

inline ll readll(){

	ll f=1,x=0;char ch=getchar();

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

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

	return x*f;

}



const int MAXN=1e6+5;

int n;

bool vis[MAXN];

int main() {

	n=read();if(n==1){puts("1");return 0;}

	deque<pii>dq;dq.pb(mk(1,1));

	while(!dq.empty()){

		pii u=dq.front();dq.pop_front();

		if(vis[u.fst])continue;

		if(u.fst==0){cout<<u.scd<<endl;return 0;}

		vis[u.fst]=1;

		dq.push_front(mk(u.fst*10%n,u.scd));

		dq.push_back(mk((u.fst+1)%n,u.scd+1));

	}return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <math.h>

#include <queue>

#define MOD 1000000007

typedef long long ll;

using namespace std;



#define INFTY (1<<30)

#define MAX 100010



int n;

vector<pair<int,int>> adj[MAX];



void dijkstra(){

  priority_queue<pair<int,int>> PQ;

  int d[MAX];

  for(int i=0;i<n;i++) d[i]=INFTY;



  d[1]=0;

  PQ.push(make_pair(0,1));



  while(!PQ.empty()){

    pair<int,int> f=PQ.top();

    //cout<<f.first<<" "<<f.second<<endl;

    PQ.pop();

    int u=f.second;



    if(d[u]<f.first*(-1)) continue;



    for(int j=0;j<adj[u].size();j++){

      int v=adj[u][j].first;

      if(d[v]>d[u]+adj[u][j].second){

        d[v]=d[u]+adj[u][j].second;

        PQ.push(make_pair(d[v]*(-1),v));

      }

    }

  }



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

  /*for(int i=0;i<n;i++){

    cout<<i<<" "<<(d[i]==INFTY?-1:d[i])<<endl;

  }*/

}



int main(){

  cin>>n;

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

    adj[i].push_back(make_pair((i+1)%n,1));

    adj[i].push_back(make_pair((i*10)%n,0));

    //cout<<i<<" "<<(i+1)%n<<" "<<i*10%n<<endl;

  }

  dijkstra();

  return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <string>

#include <vector>

#include <math.h>

#include <queue>

#include <deque>

#define MOD 1000000007

typedef long long ll;

using namespace std;



#define INFTY (1<<30)

#define MAX 100010



int main(){

  int k;

  cin>>k;



  deque<pair<int,int>> DQ;

  int d[k+1]={};

  for(int i=0;i<k;i++) d[i]=INFTY;

  DQ.push_back(make_pair(1,0));



  while(!DQ.empty()){

    pair<int,int> p=DQ.front();

    DQ.pop_front();

    int f=p.first;

    if(d[f]!=INFTY) continue;

    d[f]=p.second;



    DQ.push_front(make_pair((f*10)%k,d[f]));

    DQ.push_back(make_pair((f+1)%k,d[f]+1));

  }



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



  return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x; i <= n; i++)

#define rep3(i, x, n) for(int i = x; i >= n; i--)

#define elif else if

#define sp(x) fixed << setprecision(x)

#define pb(x) push_back(x)

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

using ll = long long;

using ld = long double;

using pii = pair<int, int>;

using pil = pair<int, ll>;

using pli = pair<ll, int>;

using pll = pair<ll, ll>;

const ll MOD = 1e9+7;

//const ll MOD = 998244353;

const int inf = 1e9;

const ll INF = 1e18;

const ld EPS = 1e-10;



struct edge{int to, cost;};



const int MAX_V = 1e5;

vector<edge> es[MAX_V];

vector<int> d(MAX_V, inf);



void add_edge(int from, int to, int cost){

    es[from].emplace_back((edge){to, cost});

}



void dijkstra(int s){

    d[s] = 0;

    queue<pii> que;

    que.push(pii(d[s], s));

    while(!que.empty()){

        pii p = que.front();

        que.pop();

        int i = p.second;

        if(p.first > d[i]) continue;

        for(auto &e: es[i]){

            if(d[e.to] > d[i]+e.cost){

                d[e.to] = d[i]+e.cost;

                que.push(pii(d[e.to], e.to));

            }

        }

    }

}



int main(){

    int K;

    cin >> K;

    rep(i, K){

        add_edge(i, (i+1)%K, 1);

        add_edge(i, (i*10)%K, 0);

    }

    dijkstra(1);

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

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

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

#define rep2(i, x, n) for(int i = x; i <= n; i++)

#define rep3(i, x, n) for(int i = x; i >= n; i--)

#define elif else if

#define sp(x) fixed << setprecision(x)

#define pb push_back

#define eb emplace_back

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

#define sz(x) (int)x.size()

using ll = long long;

using ld = long double;

using pii = pair<int, int>;

using pil = pair<int, ll>;

using pli = pair<ll, int>;

using pll = pair<ll, ll>;

const ll MOD = 1e9+7;

//const ll MOD = 998244353;

const int inf = (1<<30)-1;

const ll INF = (1LL<<60)-1;

const ld EPS = 1e-10;

template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};

template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};



int main(){

    int K;

    cin >> K;

    vector<int> es[K][2];

    rep(i, K){

        es[i][0].pb((i*10)%K);

        es[i][1].pb((i+1)%K);

    }

    int d[K];

    fill(d, d+K, inf);

    d[1] = 1;

    deque<int> que;

    que.push_back(1);

    while(!que.empty()){

        int i = que.front(); que.pop_front();

        for(auto &e: es[i][0]){

            if(chmin(d[e], d[i])) que.push_front(e);

        }

        for(auto &e: es[i][1]){

            if(chmin(d[e], d[i]+1)) que.push_back(e);

        }

    }

    cout << d[0] << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 400001;





int sum(ll n){

  int res = 0;

  while(n){

    res += n % 10;

    n /= 10;

  }

  return res;

}

bitset<100001> bb[2];

int main()

{

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

//  freopen("out.txt", "w", stdout);

  int k;

  cin >> k;

  set<int> ss;

  int x = 1;

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

    x *= 10;

    x %= k;

    ss.insert(x);

  }

  if(*ss.begin() == 0){

    cout << 1;

    return 0;

  }

  for(auto el : ss){

    bb[1][el] = 1;

  }

  int lim = sum(k);

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

    bb[i&1] = bb[i&1^1];

    for(auto el : ss){

      bb[i&1] |= (bb[i&1^1] << el);

      bb[i&1] |= (bb[i&1^1] >> (k - el));

      if(bb[i&1][0]){

//        cout << el << endl;

        cout << i;

        return 0;

      }

    }

  }

  cout << lim;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = 100001;



int bfs(int k){

  deque<int> x;

  x.push_back(1);

  int dist[100001];

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

    dist[i] = 10000;

  dist[1] = 1;

  while(x.size()){

    int u = x.front();x.pop_front();

    if(u == 0)

      return dist[u];

    if(dist[u] < dist[10 * u % k]){

      x.push_front(10 * u % k);

      dist[10 * u % k] = dist[u];

    }

    if(dist[u] + 1 < dist[(u + 1) % k]){

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

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

    }

  }

}

int main()

{

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

//  freopen("out.txt", "w", stdout);

  int k;

  cin >> k;

  cout << bfs(k);

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;



const int maxn = 100010;



char str[maxn], cur[maxn];

int len;

int l[maxn];



void init()

{

	memset(l,0,sizeof(l));

	int cnt = 0;

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

	{

		if (str[i] == '0' || i == len)

		{

			for (int j=i-cnt;j<=i-1;j++) l[j] = cnt;

			cnt = 0;

			continue;

		}

		cnt++;

	}

	//for (int i=0;i<len;i++) cout<<l[i]<<" ";

	//cout<<endl;

}



bool check(int k)

{

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

	{

		if (str[i] == '0') continue;

		if (i >= k || len-1-i>=k) continue;

		if (l[i] >= k) continue;

		return false;

	}

	return true;

}



int main()

{

	//freopen("D.in","r",stdin);

	scanf("%s",str);





	len = strlen(str);

	init();

	int lb = 1, ub = len + 1;

	while (ub > lb + 1)

	{

		int mid = (lb + ub)/2;

		if (check(mid)) lb = mid;

		else ub = mid;

	}



	for (int i=0;i<len;i++) str[i] = (str[i]=='1')?'0':'1';

	init();

	int lb2 = 1, ub2 = len + 1;

	while (ub2 > lb2 + 1)

	{

		int mid = (lb2 + ub2)/2;

		if (check(mid)) lb2 = mid;

		else ub2 = mid;

	}



	printf("%d\n",max(lb,lb2));

	return 0;

}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;



const int maxn = 100010;



char str[maxn];



int main()

{

	//freopen("D.in","r",stdin);

	scanf("%s",str);

	int len = strlen(str);



	int ans = len;

	for (int i=0;i<len-1;i++)

	{

		if (str[i] != str[i+1]) ans = min(ans, max(i+1,len-1-(i+1)+1));

	}



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

	return 0;

}


// Fastest known solution for this problem: