stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;

#define ll long long

bool isprime(ll x)

{

    for(ll i=2;i*i<=x;i++)

        if(x%i==0)

            return 0;

    //cout<<x<<endl;

    return 1;

}

int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);cout.tie(0);

    ll a,b;

    cin>>a>>b;

    ll g=__gcd(a,b);

    ll ans=0;

    for(ll i=2;i*i<=g;i++)

        if(g%i==0)

        {

            ans++;

            while(g%i==0)

                g/=i;

        }

    if(g!=1)ans++;

    cout<<ans+1<<endl;

    return 0;

}


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

#include<algorithm>

#include<cstdio>

#define N 100005

using namespace std;

long long int a[30],b[30];

long long int x,y;

int la=0,lb=0;

int main(){

scanf("%lld%lld",&x,&y);

a[++la]=1;

b[++lb]=1;

for(long long int i=2;i*i<=x;i++){

if(x%i==0){a[++la]=i;}

while(x%i==0){x/=i;}

}

if(x>1)a[++la]=x;

for(long long int i=2;i*i<=y;i++){

if(y%i==0){b[++lb]=i;}

while(y%i==0){y/=i;}

}

if(y>1)b[++lb]=y;

int z=1;

int ans=0;

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

while(b[z]<a[i]&&z<lb)z++;

if(b[z]==a[i])ans++;

}

printf("%d",ans);



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



using namespace std;



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

#define clr(v, d)       memset(v, d, sizeof(v))

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

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

#define lpi(i, j, n)    for(int i=(j); i<(int)(n); ++i)

#define lpd(i, j, n)    for(int i=(j); i>=(int)(n); --i)

#define INF             1000000000



typedef long long ll;

typedef pair<int, int> ii;

typedef vector<ii> vii;

typedef vector<int> vi;



void init(){

	std::ios_base::sync_with_stdio(false);

	cin.tie(NULL);

	cout.tie(NULL);

}



const int N = 1e6+5;

bool arr[N];



int main()

{

	init();

	ll a, b;

	int ans = 1;

	cin >> a >> b;

	a = __gcd(a, b);

	if(a % 2 == 0){

		++ans;

		while(a % 2 == 0)

			a /= 2;

	}

	b = sqrt(a);

	b = min(1000000LL, b+1);

	for (ll i = 3; i < b; i += 2) {

		if(!arr[i]){

			if(a % i == 0){

				++ans;

				while(a % i == 0)

					a /= i;

			}

			for (ll j = i * i; j < b; j += 2*i) {

		    	arr[j] = 1;

		    }

		}

	}

	if(a > 1)

		++ans;

	cout << ans;

	return 0;

}


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

#include<algorithm>

#include<cstdio>

#define N 100005

using namespace std;

long long int a[30],b[30];

long long int x,y;

int la=0,lb=0;

int main(){

scanf("%lld%lld",&x,&y);

a[++la]=1;

b[++lb]=1;

for(long long int i=2;i*i<=x;i++){

if(x%i==0){a[++la]=i;}

while(x%i==0){x/=i;}

}

if(x>1)a[++la]=x;

for(long long int i=2;i*i<=y;i++){

if(y%i==0){b[++lb]=i;}

while(y%i==0){y/=i;}

}

if(y>1)b[++lb]=y;

int z=1;

int ans=0;

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

while(b[z]<a[i]&&z<lb)z++;

if(b[z]==a[i])ans++;

}

printf("%d",ans);



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

using namespace std;



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

#define endl            "\n"

#define NUM             1000005

typedef long long ll;



map<ll,ll>mp;



void primeFactors(ll A)

{

    while(A%2==0)

    {

        mp[2]++;

        A/=2;

    }



    for(ll i=3;i<=sqrt(A);i+=2)

    {

        while(A%i==0)

        {

            mp[i]++;

            A/=i;

        }

    }



    if(A>2)

        mp[A]++;

}



int main()

{

    FastRead



    ll a,b,ans=1;



    cin>>a>>b;



    ll gcd = __gcd(a,b);



    primeFactors(gcd);



    ans+=mp.size();



    cout<<ans<<endl;

}


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

#include<algorithm>

#include<cstdio>

#define N 100005

using namespace std;

long long int a[30],b[30];

long long int x,y;

int la=0,lb=0;

int main(){

scanf("%lld%lld",&x,&y);

a[++la]=1;

b[++lb]=1;

for(long long int i=2;i*i<=x;i++){

if(x%i==0){a[++la]=i;}

while(x%i==0){x/=i;}

}

if(x>1)a[++la]=x;

for(long long int i=2;i*i<=y;i++){

if(y%i==0){b[++lb]=i;}

while(y%i==0){y/=i;}

}

if(y>1)b[++lb]=y;

int z=1;

int ans=0;

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

while(b[z]<a[i]&&z<lb)z++;

if(b[z]==a[i])ans++;

}

printf("%d",ans);



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

#include<cstdio>

#include<string.h>

#include<cmath>

#include<algorithm>

using namespace std;

#define ll long long

#define INF  0x7fffffffffff//ffff

#define M 112300

ll a[M],ans = 0,n,m;

bool check(ll x){

	if(x==2)

	return true;

	for(ll i = 2;i*i <=x;i++){

		if(x %i==0)

		return false;

	}

	return true;

}

int main(void){

	cin>>n>>m;

	if(n < m)

	swap(n,m);

	ll j = 0;

	for(ll i = 1;i *i <= m;i++){

		if(m %i==0){

			a[j] = i;

			j++;

			if(i*i!=m){

			a[j] = m/i;

			j++;

		}

		}

	}

	for(ll i = 0;i < j;i++){

		if(n % a[i]==0&&check(a[i]))

		ans++;

	}

	

	cout<<ans<<endl;

	return 0;

}

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

#include<algorithm>

#include<cstdio>

#define N 100005

using namespace std;

long long int a[30],b[30];

long long int x,y;

int la=0,lb=0;

int main(){

scanf("%lld%lld",&x,&y);

a[++la]=1;

b[++lb]=1;

for(long long int i=2;i*i<=x;i++){

if(x%i==0){a[++la]=i;}

while(x%i==0){x/=i;}

}

if(x>1)a[++la]=x;

for(long long int i=2;i*i<=y;i++){

if(y%i==0){b[++lb]=i;}

while(y%i==0){y/=i;}

}

if(y>1)b[++lb]=y;

int z=1;

int ans=0;

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

while(b[z]<a[i]&&z<lb)z++;

if(b[z]==a[i])ans++;

}

printf("%d",ans);



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

        #include<iostream>

        #include<algorithm>

        #include<set>

        #include<map>

        #include<math.h>

        //#include <ttmath.h>

        #define endl '\n'

        #define modulo 1000000007

        #define int long long

        #pragma GCC optimize("-Ofast")

        #define float double

        #define PI 3.141592653589793238462643

        #define sinDegrees(x) sin((x) * PI / 180.0)

        #define tanDegrees(x) tan((x) * PI / 180.0)

        #define atanDegrees(x) atan(x)* 180.0 / PI

        using namespace std;

        int power(int x,int y)

        {

        int temp;

        if(y == 0)

        return 1;

        temp = (power(x, y/2))%modulo;

        if (y%2 == 0)

        return ((temp%modulo)*temp)%modulo;

        else

        return ((x*temp%modulo)*temp)%modulo;

        }

        int inv(int x)

        {

        return (power(x,modulo-2)+modulo)%modulo;

        }

        /*#include "testlib.h"

        int main(int argc, char* argv[])

        {

        iostream::sync_with_stdio(0);

        cin.tie(0);

        cout.tie(0);

        registerGen(argc, argv, 1);

        int n,k;

        n=rnd.next(1,50);

        k=rnd.next(1,n);

        cout<<n<<' '<<k;

        }*/

        bool comp(pair<int,int>a,pair<int,int> b)

        {

            return a.second>b.second;

        }

        set<int>lol;

        void factorize(int n){

        if(n==1)

        return;

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

        if(n%i==0){

        factorize(n/i);

        lol.insert(i);

        return;

        }

        }

        lol.insert(n);

        }

        int32_t main()

        {

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

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

            iostream::sync_with_stdio(0);

            cin.tie(0);

            cout.tie(0);

            int a,b;

            cin>>a>>b;

            int result=(__gcd(a,b));

            factorize(result);

            cout<<lol.size()+1;

            return 0;

        }


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

#include<algorithm>

#include<cstdio>

#define N 100005

using namespace std;

long long int a[30],b[30];

long long int x,y;

int la=0,lb=0;

int main(){

scanf("%lld%lld",&x,&y);

a[++la]=1;

b[++lb]=1;

for(long long int i=2;i*i<=x;i++){

if(x%i==0){a[++la]=i;}

while(x%i==0){x/=i;}

}

if(x>1)a[++la]=x;

for(long long int i=2;i*i<=y;i++){

if(y%i==0){b[++lb]=i;}

while(y%i==0){y/=i;}

}

if(y>1)b[++lb]=y;

int z=1;

int ans=0;

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

while(b[z]<a[i]&&z<lb)z++;

if(b[z]==a[i])ans++;

}

printf("%d",ans);



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

}


// Faster C++ solution for the same problem (measured speedup: 2.075253907423251x):
#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;

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

}

// Faster C++ solution for the same problem (measured speedup: 3.48305542609472x):
#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;

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

}




// Faster C++ solution for the same problem (measured speedup: 10.338644487070056x):
#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;

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

}




// Faster C++ solution for the same problem (measured speedup: 10.33435706803268x):
#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;

    deque<int> deq = {1};

    while(v = deq.front()){

        deq.pop_front();

        u = (v*10)%k;

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

            dp[u] = dp[v];

            deq.push_front(u);

        }

        u = (v+1)%k;

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

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

            deq.push_back(u);

        }

    }

    cout<<dp[v]<<endl;

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

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

}

// Faster C++ solution for the same problem (measured speedup: 1.382425004785474x):
#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;

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

}


// Faster C++ solution for the same problem (measured speedup: 1.3954300090240368x):
#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;

}