#include<bits/stdc++.h>

using namespace std;

int k;

deque<pair<long long,int> >q;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin>>k;
	
	q.push_back(make_pair(1,1));
	while(!q.empty())
	{
		long long x=q.front().first;
		int step=q.front().second;
		q.pop_front();
		if(x/k>=10)continue;
		if(x%k==0)
		{
			cout<<step<<'\n';return 0;
		}
		q.push_front(make_pair(x*10,step));
		q.push_back(make_pair(x+1,step+1));
	}

	return 0;
}