// LUOGU_RID: 111577246
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans=LLONG_MAX;
const double eps=1e-5;
mt19937 rnd(114514);
int count(int x)
{
	int sum=0;
	while(x)
	{
		sum+=x%10;
		x/=10;
	}
	return sum;
}
void fire()
{
	int t=10000;
	int nxt,now,oh=0,good;
	while(t>eps)
	{
		nxt=oh+rnd()%100000000+1;
		now=count(nxt*n);
		good=ans-now;
		if(good>0) ans=now,oh=now;
		else if(exp(good*1.0/t)*100000000ll>rnd()) oh=now;
		t*=0.996;
	}
}
signed main()
{
	cin>>n;
	int start=clock();
	ans=count(n);
	while((clock()-start)*1.0/CLOCKS_PER_SEC<1.9) fire();
	cout<<ans;
	return 0;
}