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

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

using namespace std;

using ll = long long;



int main() {

  int n;

  cin >> n;

  vector<ll>f(n+1);

  int div=1;

  while (div<=n) {

    int i=1;

    while (div*i<=n) {

      f[div*i]+=div*i;

      i++;

    }

    div++;

  }

  ll ans=0;

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

    ans+=f[i];

  }

  cout << ans << endl;

}


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

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

using namespace std;

using ll = long long;



int main() {

  int n;

  cin >> n;

  int div[n+1];

  ll ans=0;

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

    ll d=n/i;

    ans+=i*(d+1)*d/2;

  }

  cout << ans << endl;

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

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

using namespace std;

using ll = long long;



int main() {

  int n;

  cin >> n;

  vector<ll>f(n+1);

  int div=1;

  while (div<=n) {

    int i=1;

    while (div*i<=n) {

      f[div*i]+=div*i;

      i++;

    }

    div++;

  }

  ll ans=0;

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

    ans+=f[i];

  }

  cout << ans << endl;

}


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

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

using namespace std;

using ll = long long;



int main() {

  int n;

  cin >> n;

  ll ans=0;

  int y;

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

    ll d=n/i;

    ans+=i*(d+1)*d/2;

    y=i;

  }

  int z=n/(y+1);

  for (ll i=1;i<=z;i++) {

      ll low=n/(i+1);

      ll high=n/i;

      ll x=high*(high+1)/2-low*(low+1)/2;

      ans+=x*i*(i+1)/2;

  }

  cout << ans << endl;

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

#include<string>

using namespace std;

typedef long long int ll;

#pragma GCC optimize "trapv"

#define fi first

#define sec second

#define pb push_back

//#define endl '\n'

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);



void solve(){

	int  n;

	cin>>n;

	vector<bool> pr(n+1,1);

	vector<ll> div(n+1,1);

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

		if(pr[i]){

			div[i]=2;

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

				pr[k*i]=0;

				int count=0;

				int temp=k*i;

				while(temp%i==0){

					temp/=i;

					count++;

				}

				div[k*i]*=count+1;

			}

		}

	}

	ll ans=0;

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

		ans+=(ll(i))*div[i];

	}

	cout<<ans<<endl;

}

int main(){

	fio;

	int test;

	//cin>>test;

	test=1;

	while(test--){

		solve();

	}

	return 0;

}


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

#include<string>

using namespace std;

typedef long long int ll;

//#pragma GCC optimize "trapv"

#define fi first

#define sec second

#define pb push_back

//#define endl '\n'

#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);



void solve(){

	int  n;

	cin>>n;

	vector<bool> pr(n+1,1);

	vector<ll> div(n+1,1);

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

		if(pr[i]){

			div[i]=2;

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

				pr[k*i]=0;

				int count=0;

				int temp=k*i;

				while(temp%i==0){

					temp/=i;

					count++;

				}

				div[k*i]*=count+1;

			}

		}

	}

	ll ans=0;

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

		ans+=(ll(i))*div[i];

	}

	cout<<ans<<endl;

}

int main(){

	fio;

	int test;

	//cin>>test;

	test=1;

	while(test--){

		solve();

	}

	return 0;

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

using namespace std;

int n,a[100005];

int main() {

    scanf("%d",&n);

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

        scanf("%d",&x),a[i]=(i==x);

    }

    int ans=0;

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

        if (a[i]) a[i]=a[i+1]=0,++ans;

    }

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

}


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



int main()

{

	int N,i;

	int s[100005]={0};

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

	{

		int q=0;

		int t=0;

		for(i=1;i<=N;i++)

		{

			scanf("%d",&s[i]);

		}

		

		for(i=1;i<=N;i++)

		{

			if(s[i]==i)

			{

				int x;

				x=s[i];

				s[i]=s[i+1];

				s[i+1]=x;

				t++;

			}

		}

		if(s[N]==N) t++;

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

	}

	

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

using namespace std;

int n,a[100005];

int main() {

    scanf("%d",&n);

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

        scanf("%d",&x),a[i]=(i==x);

    }

    int ans=0;

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

        if (a[i]) a[i]=a[i+1]=0,++ans;

    }

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

}


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

using namespace std;

int main(){

	int a[100050]={0},b[100050],c,i,j,n,m;

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

	int times=0;

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

		if(a[i]==i){

			c=a[i];

			a[i]=a[i+1];

			a[i+1]=c;

			times++;

		}

	}	

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

	return 0;

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

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

	int n;

	while(cin>>n)

	{

		int a[100000];

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

		{

			cin>>a[i];

		}

		int sum=0;

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

		{

			if(a[i]==i)

			{

				int t=a[i];a[i]=a[i+1];a[i+1]=t;

				sum++;

			}

		}

		cout<<sum<<"\n";

	}

}

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

using namespace std;

int main(){

	int a[100050]={0},b[100050],c,i,j,n,m;

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

	int times=0;

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

		if(a[i]==i){

			c=a[i];

			a[i]=a[i+1];

			a[i+1]=c;

			times++;

		}

	}	

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

	return 0;

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

#include<cstdio>

#include<algorithm>

#include<vector>

#include<cstring>

#include<cmath>

using namespace std;

int main()

{

	int n,i,j,a,b,c=0,t;

	vector<int> v;

	cin >> n;

	for(i=0;i<n;i++)

	{

		cin >> a;

		v.push_back(a);

	}

	for(i=0;i<n;i++)

	{

		if(i==0&&v[i]==1)

		{

			for(j=1;j<n;j++)

			if(v[j]!=1)

			{t=v[i];v[i]=v[j];v[j]=t;c+=j;break;}

		}

		else if(i==n-1&&v[i]==n)

		{

			for(j=n-2;j>=0;j--)

			if(v[j]!=n)

			{t=v[i];v[i]=v[j];v[j]=t;c+=n-1-j;break;}

		}

		else if(i<n-1&&i>0)

		{

			if(i+1==v[i])

			{

				for(j=i+1;j<n;j++)

				if(v[j]!=i+1)

				{a=j;break;}

				for(j=i-1;j>=0;j--)

				if(v[j]!=i+1)

				{b=j;break;}

				if(a-i>i-b) j=b;

				else j=a;

				{t=v[i];v[i]=v[j];v[j]=t;c+=abs(j-i);}

			}

		}

	}

	cout << c;

	return 0;

}

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

using namespace std;

int main(){

	int a[100050]={0},b[100050],c,i,j,n,m;

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

	int times=0;

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

		if(a[i]==i){

			c=a[i];

			a[i]=a[i+1];

			a[i+1]=c;

			times++;

		}

	}	

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

	return 0;

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

using namespace std;

const int maxn=1e5+10;

int a[maxn];

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

{

	int n;

	cin>>n;

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

	  cin>>a[i];

	 int sum=0; 

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

		if(a[i]==i+1){

			int t=a[i];

			a[i]=a[i+1];

			a[i+1]=t;

			sum++;

		}

	}  

	for(int i=n-1;i>=0;i--){

		if(a[i]==i+1){

			int t=a[i];

			a[i]=a[i+1];

			a[i+1]=t;

			sum++;

		}

	}  

	cout<<sum<<endl;

	return 0;

}

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

using namespace std;

int main(){

	int a[100050]={0},b[100050],c,i,j,n,m;

	scanf("%d",&n);

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

		scanf("%d",&a[i]);

	}

	int times=0;

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

		if(a[i]==i){

			c=a[i];

			a[i]=a[i+1];

			a[i+1]=c;

			times++;

		}

	}	

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

	return 0;

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

#include<vector>

#include<map>

#include<climits>

#include<algorithm>

using namespace std;

typedef pair<int,int> Pt;

#define MAX 1000001

#define fr first

#define sc second

int n,dat[MAX * 2 - 1];

void update(int i,int x){

  i += n - 1;

  dat[i] = x;

  while(i > 0){

    i = (i - 1)/2;

    dat[i] = min(dat[i*2+1],dat[i*2+2]);

  }

}

int query(int a,int b,int k,int l,int r){

  if( r<=a || b <= l ) return INT_MAX;

  if( a<=l && r <= b ) return dat[k];

  return min(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));

}

int main(){

  int q,a,b,c,N;

  for(int i=0;i<MAX*2-1;i++) dat[i] = INT_MAX;

  scanf("%d %d",&N,&q);

  n=1;

  while(n < N) n *= 2;

  while(q--){

    scanf("%d %d %d",&a,&b,&c);

    if(!a) update(b,c);

    else printf("%d\n",query(b,c+1,0,0,n));

  }

}

// Faster C++ solution for the same problem (measured speedup: 44.3191903019101x):
// RMQ (Range Minimum Query)

#include<cstdio>

#include<algorithm>

#include<climits>

using namespace std;

#define MAX ( 1 << 17 )

const int INF = INT_MAX;

int n, seg[MAX * 2 - 1];

void update( int i, int x){

  i += n - 1;

  seg[i] = x;

  while(i > 0){

    i = ( i - 1 ) / 2;

    seg[i] = min( seg[i * 2 + 1], seg[i * 2 + 2]);

  }

}

int query( int a, int b, int k, int l, int r){

  if( r <= a || b <= l ) return INF;

  if( a <= l && r <= b ) return seg[k];

  int vl = query( a, b, k * 2 + 1, l, (l + r) / 2);

  int vr = query( a, b, k * 2 + 2, (l + r) / 2, r);

  return min( vl, vr);

}

void init( int& size){

  n = 1;

  while( n < size ) n *= 2;

  fill_n( seg, n * 2 - 1, INF);

}

int main(){

  int size, q;

  scanf("%d %d", &size, &q);

  init(size);

  while(q--){

    int com, a, b;

    scanf("%d %d %d", &com, &a, &b);

    if( com == 0 ) update( a, b);

    else printf("%d\n", query( a, b + 1, 0, 0, n));

  }

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

#include <iostream>

#include <algorithm>

using namespace std;



inline int nextInt(void) {

	register int ret = 0;

	register int neg = false;

	register int bit = getchar();

	

	for (; bit < '0'; bit = getchar())

		if (bit == '-')neg ^= true;

	

	for (; bit >= '0'; bit = getchar())

		ret = ret * 10 + bit - '0';

	

	return neg ? -ret : ret;

}



#define inf 2147483647



int n, m, mini[400005];



int find(int t, int l, int r, int x, int y) {

	if (x <= l && r <= y)

		return mini[t];

	int mid = (l + r) >> 1;

	if (y <= mid)

		return find(t << 1, l, mid, x, y);

	if (x > mid)

		return find(t << 1 | 1, mid + 1, r, x, y);

	else

		return min(

			find(t << 1, l, mid, x, mid),

			find(t << 1 | 1, mid + 1, r, mid + 1, y)

		);

}



void update(int t, int l, int r, int x, int y) {

	if (l == r)mini[t] = y;

	else {

		int mid = (l + r) >> 1;

		if (x <= mid)

			update(t << 1, l, mid, x, y);

		else

			update(t << 1 | 1, mid + 1, r, x, y);

		mini[t] = min(mini[t << 1], mini[t << 1 | 1]);

	}

}



signed main(void) {

	n = nextInt();

	m = nextInt();



	for (int i = 0; i <= (n << 2); ++i)mini[i] = inf;



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

		int c = nextInt();

		int x = nextInt();

		int y = nextInt();

		if (c)	// find(x, y)

			printf("%d\n", find(1, 1, n, x + 1, y + 1));

		else	// update(x, y)

			update(1, 1, n, x + 1, y);

	}



//	system("pause");

}

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



inline int min(const int &a, const int &b) {

	return a < b ? a : b;

}



#define siz 10000000



char buf[siz], *bit = buf;



inline int nextInt(void) {

	register int ret = 0;

	register int neg = false;

	

	for (; *bit < '0'; ++bit)

		if (*bit == '-')neg ^= true;

	

	for (; *bit >= '0'; ++bit)

		ret = ret * 10 + *bit - '0';

	

	return neg ? -ret : ret;

}



#define inf 2147483647



int n, m, mini[400005];



int find(int t, int l, int r, int x, int y) {

	if (x <= l && r <= y)

		return mini[t];

	int mid = (l + r) >> 1;

	if (y <= mid)

		return find(t << 1, l, mid, x, y);

	if (x > mid)

		return find(t << 1 | 1, mid + 1, r, x, y);

	else

		return min(

			find(t << 1, l, mid, x, mid),

			find(t << 1 | 1, mid + 1, r, mid + 1, y)

		);

}



void update(int t, int l, int r, int x, int y) {

	if (l == r)mini[t] = y;

	else {

		int mid = (l + r) >> 1;

		if (x <= mid)

			update(t << 1, l, mid, x, y);

		else

			update(t << 1 | 1, mid + 1, r, x, y);

		mini[t] = min(mini[t << 1], mini[t << 1 | 1]);

	}

}



signed main(void) {

	fread(buf, 1, siz, stdin);



	n = nextInt();

	m = nextInt();



	for (int i = 0; i <= (n << 2); ++i)mini[i] = inf;



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

		int c = nextInt();

		int x = nextInt();

		int y = nextInt();

		if (c)	// find(x, y)

			printf("%d\n", find(1, 1, n, x + 1, y + 1));

		else	// update(x, y)

			update(1, 1, n, x + 1, y);

	}



//	system("pause");

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

using namespace std;



#define INF 2147483647

//1024*1024*1024*2-1

#define ASTART (1<<17)

int a[1<<18];



void update(int i,int x){

  i+=ASTART-1;

  a[i]=x;

  //cout << i << " = " << a[i];

  while (i>0){

    i=(i-1)/2;

    a[i]=min(a[i*2+1],a[i*2+2]);

  }

}

int find(int s,int t,int k,int l,int r){

  if (r<=s||l>=t)return INF;

  if (l>=s&&r<=t)return a[k];

  int m=(l+r)/2;

  return min(find(s,t,k*2+1,l,m),find(s,t,k*2+2,m,r));

}



int main(){

  int n,q,com,x,y;

  for (int i=0;i<262150;i++)a[i]=INF;

  cin >> n>>q;



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

    cin >> com >> x >> y;

    if (com==0) update(x,y);

    else cout << find(x,y+1,0,0,ASTART)<< endl;

    //for (int i=0;i<5;i++)cout << a[i] << endl;

    //cout << a[ASTART];

  }



  return 0;

}

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

using namespace std;



#define INF (1 << 30) - 1 + (1 << 30)



int a[262144], n2;



void update(int i, int x) {

  i += n2 - 1;

  a[i] = x;

  while (i > 0) {

    i = (i - 1) / 2;

    a[i] = min(a[i * 2 + 1], a[i * 2 + 2]);

  }

}



int find(int s, int t, int i, int l, int r) {

  if (s <= l && r <= t) return a[i];

  if (t <= l || r <= s) return INF;

  int cl, cr;

  cl = find(s, t, i * 2 + 1, l, (l + r) / 2);

  cr = find(s, t, i * 2 + 2, (l + r) / 2, r);

  return min(cl, cr);

}



int main() {

  int n, q, com, x, y;



  cin >> n >> q;

  n2 = 1;

  while (n > n2) n2 *= 2;

  for (int i = 0; i < n2*2; i++) a[i] = INF;



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

    cin >> com >> x >> y;

    if (com == 0)

      update(x, y);

    else

      cout << find(x, y + 1, 0, 0, n2) << endl;

  }

  return 0;

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

using namespace std;



const int MAX = 1 << 17;



int main()

{

	ios::sync_with_stdio(false), cin.tie(0);

	int n, q;

	cin >> n >> q;

	vector<int> v(MAX << 1, INT_MAX);

	while (q--) {

		int com, x, y;

		cin >> com >> x >> y;

		if (com == 0) {

			for (v[x += MAX] = y; x >>= 1;) {

				v[x] = min(v[x << 1], v[(x << 1) | 1]);

			}

		}

		else {

			int res = INT_MAX;

			for (x += MAX, y += MAX + 1; x < y; x >>= 1, y >>= 1) {

				if (x & 1) res = min(res, v[x++]);

				if (y & 1) res = min(res, v[--y]);

			}

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

		}

	}

	return 0;

}




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

using namespace std;



const int id = INT_MAX;



int op(int l, int r) {

	return min(l, r);

}



struct node {

	int pos, val, all;

	node *lch, *rch;

	node(int p, int v)

		: pos(p), val(v), all(v), lch(nullptr), rch(nullptr) {}

};



void update_up(node* t) {

	t->all = op(op((t->lch ? t->lch->all : id), t->val), (t->rch ? t->rch->all : id));

}



node *update(node* t, int p, int val, int lb, int ub) {

	if (!t) return new node(p, val);

	if (t->pos == p) {

		t->val = val;

		update_up(t);

		return t;

	}

	int m = (lb + ub) >> 1;

	if (p < m) {

		t->lch = update(t->lch, p, val, lb, m);

	}

	else {

		t->rch = update(t->rch, p, val, m, ub);

	}

	update_up(t);

	return t;

}



int find(node* t, int l, int r, int lb, int ub) {

	if (!t || r <= lb || ub <= l) return id;

	if (l <= lb && ub <= r) return t->all;

	int m = (lb + ub) >> 1;

	return op(op(find(t->lch, l, r, lb, m), find(t->rch, l, r, m, ub)), l <= t->pos && t->pos < r ? t->val : id);

}



int main()

{

	int n, q;

	scanf("%d%d", &n, &q);

	node *seg = nullptr;

	while (q--) {

		int com, x, y;

		scanf("%d%d%d", &com, &x, &y);

		if (com == 0) {

			seg = update(seg, x, y, 0, n);

		}

		else {

			printf("%d\n", find(seg, x, y + 1, 0, n));

		}

	}

	return 0;

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

using namespace std;



template<typename T, int M>

struct RMQ {

    T arr[M];

    T INF;

    int N;

    

    RMQ(int N_, T INF_) {

        INF = INF_;

        for (int j = 0; j < M; ++j) {

            arr[j] = INF;

        }



        N = 1;

        while (N < N_) N *= 2;

    }



    void update(int x, int a) {

        int ind = N - 1 + x;



        arr[ind] = a;



        while (ind > 0) {

            ind = (ind - 1) / 2;

            arr[ind] = min(arr[ind*2 + 1], arr[ind*2 + 2]);

        }

    }



    T query(int x, int y) {

        return query_(x, y, 0, 0, N);

    }

    

    T query_(int x, int y, int v, int l, int r) {

        if (y <= l || r <= x) return INF;



        if (x <= l && r <= y) return arr[v];



        T vl = query_(x, y, 2*v + 1, l, (l + r) / 2);

        T vr = query_(x, y, 2*v + 2, (l + r) / 2, r);



        return vl < vr ? vl : vr;

    }

};



int main() {

    int n, q;

    cin >> n >> q;

    RMQ<int, 300000> rmq(n, ((1 << 30) - 1) * 2 + 1);



    for (int j = 0; j < q; ++j) {

        int com, x, y;

        cin >> com >> x >> y;



        if (com == 0) {

            rmq.update(x, y);

        }



        if (com == 1) {

            int res = rmq.query(x, y+1);

            cout << res << endl;

        }

    }



    return 0;

}

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

#include <iostream>

using namespace std;



constexpr int INF = (1LL << 31) - 1;



template<typename T, int MAX_N>

struct segment_tree_min {

    int N;

    T arr[MAX_N << 1];



    segment_tree_min(int n, T INF) {

        N = 1;

        while (N < n) N *= 2;



        for (int i = 0; i < 2*N-1; ++i) {

            arr[i] = INF;

        }

    }



    void update(int i, T v) {

        int j = i + N-1;



        arr[j] = v;

        while (j > 0) {

            j = (j-1) / 2;

            arr[j] = min(arr[2*j+1], arr[2*j+2]);

        }

    }



    T query(int a, int b) {

        return query(a, b, 0, 0, N);

    }



    T query(int a, int b, int k, int l, int r) {

        if (b <= l || r <= a) return INF;

        if (a <= l && r <= b) return arr[k];



        const int m = (l+r)/2;

        return min(query(a, b, 2*k+1, l, m), query(a, b, 2*k+2, m, r));

    }

};



int main() {

    cin.tie(0); ios::sync_with_stdio(false);

    int N, Q;

    cin >> N >> Q;

    segment_tree_min<int, 202020> segt(N, INF);

    for (int j = 0; j < Q; ++j) {

        int c, x, y;

        cin >> c >> x >> y;

        if (c == 0) {

            segt.update(x, y);

        } else {

            cout << segt.query(x, y+1) << endl;

        }

    }



    return 0;

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

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

using namespace std;

const int INF=1<<29;

/*

Status:Writing

Type:Problemset/HB

Problem ID:Atcoder/ARC/84

Author:XIZCM

*/

int k;

deque<int> dq;

int d[100005];

int main(){

	cin>>k;

	fill(d,d+100005,INF);

	d[1]=1;

	dq.push_front(1);

	while(!dq.empty()){

		int t=dq.front();

		dq.pop_front();

		if(d[(t*10)%k]>d[t]){

			d[(t*10)%k]=d[t];

			dq.push_front((t*10)%k);

		}

		if(d[(t+1)%k]>d[t]+1){

			d[(t+1)%k]=d[t]+1;

			dq.push_back((t+1)%k);

		}

	}

	cout<<d[0]<<endl;

	return 0;

}


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

#include <map>

#include <set>

#include <deque>

#include <queue>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

using namespace std;

const int INF=1<<29;

/*

Status:Writing

Type:Problemset/HB

Problem ID:Atcoder/ARC/84

Author:XIZCM

*/

int k;

deque<int> dq;

int d[100005];

int main(){

	cin>>k;

	fill(d,d+100005,INF);

	d[1]=1;

	dq.push_front(1);

	while(!dq.empty()){

		int t=dq.front();

		dq.pop_front();

		if(d[(t*10)%k]>d[t]){

			d[(t*10)%k]=d[t];

			dq.push_front((t*10)%k);

		}

		if(d[(t+1)%k]>d[t]+1){

			d[(t+1)%k]=d[t]+1;

			dq.push_back((t+1)%k);

		}

	}

	cout<<d[0]<<endl;

	return 0;

}


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

#include <bitset>

#include <complex>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <iterator>

#include <limits>

#include <list>

#include <locale>

#include <map>

#include <memory>

#include <new>

#include <numeric>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <typeinfo>

#include <utility>

#include <valarray>

#include <vector>

using namespace std;

const int MOD=1000000007;

int K,dist[100000];

deque<int> tobo;

int main()

{

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cin >>K;

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

	{

		dist[i]=MOD;

	}

	dist[1]=1;

	tobo.push_back(1);

	while(tobo.size())

	{

		int x=tobo.front();

		tobo.pop_front();

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

		{

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

			tobo.push_back((10*x)%K);

		}

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

		{

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

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

		}

	}

	cout <<dist[0];

    return 0;

}