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

using namespace std;

#define F(i,a,b) for(int i=a;i<=(b);++i)

#define ll long long

int k,a[100001],vis[100001];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;

int c[100001];

int main(){

	scanf("%d",&k);

	memset(a,0x3f,sizeof a);

	a[1]=1; pq.push(make_pair(1,1));

	while(!pq.empty()){

		pair<int,int> P=pq.top(); pq.pop();

		int u=P.second, d=P.first;

		if(vis[u]) continue;

		int v=(u+1)%k;

		if(a[v]>d+1) a[v]=d+1, pq.push(make_pair(a[v],v));

		for(int i=u;;i=i*10%k){

			if(c[i]||vis[i]) break;

			if(a[i]>d) a[i]=d, pq.push(make_pair(a[i],i));

			c[i]=1;

		}

		for(int i=u;;i=i*10%k){

			if(!c[i]) break;

			c[i]=0;

		}

		vis[u]=1;

	} printf("%d",a[0]);

	return 0;

}

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

using namespace std;



typedef long long LL;

typedef pair<int, int> PII;

typedef vector<int> VI;

#define MP make_pair

#define PB push_back

#define X first

#define Y second



#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)

#define ALL(a) a.begin(), a.end()

#define SZ(a) (int)((a).size())

#define FILL(a, value) memset(a, value, sizeof(a))

#define debug(a) cerr << #a << " = " << a << endl;



const double PI = acos(-1.0);

const LL INF = 1e9 + 47;

const LL LINF = INF * INF;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());



namespace FastNTT

{

	const int MOD = 998244353;

	 

	struct mod_int {

		int val;

	 

		mod_int(long long v = 0) {

			if (v < 0) v = v % MOD + MOD;

			if (v >= MOD) v %= MOD;

			val = v;

		}

	 

		static int mod_inv(int a, int m = MOD) {

			// https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example

			int g = m, r = a, x = 0, y = 1;

	 

			while (r != 0) {

				int q = g / r;

				g %= r; swap(g, r);

				x -= q * y; swap(x, y);

			}

	 

			return x < 0 ? x + m : x;

		}

	 

		explicit operator int() const {

			return val;

		}

	 

		mod_int& operator+=(const mod_int &other) {

			val += other.val;

			if (val >= MOD) val -= MOD;

			return *this;

		}

	 

		mod_int& operator-=(const mod_int &other) {

			val -= other.val;

			if (val < 0) val += MOD;

			return *this;

		}

	 

		static unsigned fast_mod(uint64_t x, unsigned m = MOD) {

	#if !defined(_WIN32) || defined(_WIN64)

			return x % m;

	#endif

			// Optimized mod for Codeforces 32-bit machines.

			// x must be less than 2^32 * m for this to work, so that x / m fits in a 32-bit integer.

			unsigned x_high = x >> 32, x_low = (unsigned) x;

			unsigned quot, rem;

			asm("divl %4\n"

				: "=a" (quot), "=d" (rem)

				: "d" (x_high), "a" (x_low), "r" (m));

			return rem;

		}

	 

		mod_int& operator*=(const mod_int &other) {

			val = fast_mod((uint64_t) val * other.val);

			return *this;

		}

	 

		mod_int& operator/=(const mod_int &other) {

			return *this *= other.inv();

		}

	 

		friend mod_int operator+(const mod_int &a, const mod_int &b) { return mod_int(a) += b; }

		friend mod_int operator-(const mod_int &a, const mod_int &b) { return mod_int(a) -= b; }

		friend mod_int operator*(const mod_int &a, const mod_int &b) { return mod_int(a) *= b; }

		friend mod_int operator/(const mod_int &a, const mod_int &b) { return mod_int(a) /= b; }

	 

		mod_int& operator++() {

			val = val == MOD - 1 ? 0 : val + 1;

			return *this;

		}

	 

		mod_int& operator--() {

			val = val == 0 ? MOD - 1 : val - 1;

			return *this;

		}

	 

		mod_int operator++(int) { mod_int before = *this; ++*this; return before; }

		mod_int operator--(int) { mod_int before = *this; --*this; return before; }

	 

		mod_int operator-() const {

			return val == 0 ? 0 : MOD - val;

		}

	 

		bool operator==(const mod_int &other) const { return val == other.val; }

		bool operator!=(const mod_int &other) const { return val != other.val; }

	 

		mod_int inv() const {

			return mod_inv(val);

		}

	 

		mod_int pow(long long p) const {

			assert(p >= 0);

			mod_int a = *this, result = 1;

	 

			while (p > 0) {

				if (p & 1)

					result *= a;

	 

				a *= a;

				p >>= 1;

			}

	 

			return result;

		}

	 

		friend ostream& operator<<(ostream &stream, const mod_int &m) {

			return stream << m.val;

		}

	};

	 

	namespace NTT {

		vector<mod_int> roots = {0, 1};

		vector<int> bit_reverse;

		int max_size = -1;

		mod_int root;

	 

		bool is_power_of_two(int n) {

			return (n & (n - 1)) == 0;

		}

	 

		int round_up_power_two(int n) {

			while (n & (n - 1))

				n = (n | (n - 1)) + 1;

	 

			return max(n, 1);

		}

	 

		// Given n (a power of two), finds k such that n == 1 << k.

		int get_length(int n) {

			assert(is_power_of_two(n));

			return __builtin_ctz(n);

		}

	 

		// Rearranges the indices to be sorted by lowest bit first, then second lowest, etc., rather than highest bit first.

		// This makes even-odd div-conquer much easier.

		void bit_reorder(int n, vector<mod_int> &values) {

			if ((int) bit_reverse.size() != n) {

				bit_reverse.assign(n, 0);

				int length = get_length(n);

	 

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

					bit_reverse[i] = (bit_reverse[i >> 1] >> 1) + ((i & 1) << (length - 1));

			}

	 

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

				if (i < bit_reverse[i])

					swap(values[i], values[bit_reverse[i]]);

		}

	 

		void find_root() {

			max_size = 1 << __builtin_ctz(MOD - 1);

			root = 2;

	 

			// Find a max_size-th primitive root of MOD.

			while (!(root.pow(max_size) == 1 && root.pow(max_size / 2) != 1))

				root++;

		}

	 

		void prepare_roots(int n) {

			if (max_size < 0)

				find_root();

	 

			assert(n <= max_size);

	 

			if ((int) roots.size() >= n)

				return;

	 

			int length = get_length(roots.size());

			roots.resize(n);

	 

			// The roots array is set up such that for a given power of two n >= 2, roots[n / 2] through roots[n - 1] are

			// the first half of the n-th primitive roots of MOD.

			while (1 << length < n) {

				// z is a 2^(length + 1)-th primitive root of MOD.

				mod_int z = root.pow(max_size >> (length + 1));

	 

				for (int i = 1 << (length - 1); i < 1 << length; i++) {

					roots[2 * i] = roots[i];

					roots[2 * i + 1] = roots[i] * z;

				}

	 

				length++;

			}

		}

	 

		void fft_iterative(int N, vector<mod_int> &values) {

			assert(is_power_of_two(N));

			prepare_roots(N);

			bit_reorder(N, values);

	 

			for (int n = 1; n < N; n *= 2)

				for (int start = 0; start < N; start += 2 * n)

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

						mod_int even = values[start + i];

						mod_int odd = values[start + n + i] * roots[n + i];

						values[start + n + i] = even - odd;

						values[start + i] = even + odd;

					}

		}

	 

		const int FFT_CUTOFF = 150;

	 

		vector<mod_int> mod_multiply(vector<mod_int> left, vector<mod_int> right) {

			int n = left.size();

			int m = right.size();

	 

			// Brute force when either n or m is small enough.

			if (min(n, m) < FFT_CUTOFF) {

				const uint64_t ULL_BOUND = numeric_limits<uint64_t>::max() - (uint64_t) MOD * MOD;

				vector<uint64_t> result(n + m - 1, 0);

	 

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

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

						result[i + j] += (uint64_t) ((int) left[i]) * ((int) right[j]);

	 

						if (result[i + j] > ULL_BOUND)

							result[i + j] %= MOD;

					}

	 

				for (uint64_t &x : result)

					if (x >= MOD)

						x %= MOD;

	 

				return vector<mod_int>(result.begin(), result.end());

			}

	 

			int N = round_up_power_two(n + m - 1);

			left.resize(N);

			right.resize(N);

	 

			bool equal = left == right;

			fft_iterative(N, left);

	 

			if (equal)

				right = left;

			else

				fft_iterative(N, right);

	 

			mod_int inv_N = mod_int(N).inv();

	 

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

				left[i] *= right[i] * inv_N;

	 

			reverse(left.begin() + 1, left.end());

			fft_iterative(N, left);

			left.resize(n + m - 1);

			return left;

		}

	 

		vector<mod_int> mod_power(const vector<mod_int> &v, int exponent) {

			assert(exponent >= 0);

			vector<mod_int> result = {1};

	 

			if (exponent == 0)

				return result;

	 

			for (int k = 31 - __builtin_clz(exponent); k >= 0; k--) {

				result = mod_multiply(result, result);

	 

				if (exponent >> k & 1)

					result = mod_multiply(result, v);

			}

	 

			return result;

		}

	 

		vector<mod_int> mod_multiply_all(const vector<vector<mod_int>> &polynomials) {

			if (polynomials.empty())

				return {1};

	 

			struct compare_size {

				bool operator()(const vector<mod_int> &x, const vector<mod_int> &y) {

					return x.size() > y.size();

				}

			};

	 

			priority_queue<vector<mod_int>, vector<vector<mod_int>>, compare_size> pq(polynomials.begin(), polynomials.end());

	 

			while (pq.size() > 1) {

				vector<mod_int> a = pq.top(); pq.pop();

				vector<mod_int> b = pq.top(); pq.pop();

				pq.push(mod_multiply(a, b));

			}

	 

			return pq.top();

		}

	};



};



using namespace FastNTT;



namespace IntModulo

{

	const int mod = 1e9 + 7;



	inline int add(int x, int y, int m = mod)

	{

		if (x + y < m)

			return x + y;

		return x + y - m;

	}



	inline int sub(int x, int y, int m = mod)

	{

		if (x >= y)

			return x - y;

		return x - y + m;

	}



	inline int mult(int x, int y, int m = mod)

	{

		return x * (LL) y % m;

	}



	inline int power(int x, int y, int m = mod)

	{

		int r = 1;

		while(y)

		{

			if (y & 1)

				r = mult(r, x, m);

			x = mult(x, x, m);

			y >>= 1;

		}

		

		return r;

	}

	

	inline int inverse(int x, int m = mod)

	{

		return power(x, m - 2, m);

	}

	

	inline void ADD(int& x, int y, int m = mod)

	{

		x += y;

		if (x >= m) x -= m;

	}

	

	inline void SUB(int& x, int y, int m = mod)

	{

		x -= y;

		if (x < 0) x += m;

	}

	

	inline void MULT(int& x, int y, int m = mod)

	{

		x = x * (LL) y % m;

	}

};



inline int compress(int n)

{

	int r = n;

	while(r % 2 == 0) r /= 2;

	while(r % 5 == 0) r /= 5;

	return r;

}



inline int sum(LL n)

{

	int res = 0;

	while(n)

	{

		res += n % 10;

		n /= 10;

	}

	return res;

}



int get(int n, int iter)

{

	int res = INF;

	for(LL i = n; i <= n *(LL) iter; i += n)

		res = min(res, sum(i));

	return res;

}



vector<int> generate(int n)

{

	vector<int> is(n, 0);

	int pw = 1;

	FOR(it, 0, n)

	{

		pw = IntModulo::mult(pw, 10, n);

		is[pw] = true;

	}	

	

	return is;

}



vector<int> multiply(vector<int>& l, vector<int>& r)

{

	vector<mod_int> L(SZ(l));

	vector<mod_int> R(SZ(r));

	FOR(i, 0, SZ(l)) L[i] = l[i];

	FOR(i, 0, SZ(r)) R[i] = r[i];

	auto res = NTT::mod_multiply(L, R);

	vector<int> ans(SZ(res));

	FOR(i, 0, SZ(ans)) ans[i] = (int)res[i];

	return ans;

}



int solve(int k)

{

	k = compress(k);

	if (k == 1) return 1;

	vector<int> is = generate(k);

	vector<int> is_copy = generate(k);

	

	FOR(it, 2, 46)

	{

		auto tut = multiply(is, is_copy);

		is.assign(k, 0);

		FOR(i, 0, SZ(tut)) if (tut[i])

			is[i % k] = true;

			

		if (is[0] == 1) 

			return it;

	}

	

	

	assert(false);

}



int main()

{

	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	

	int n;

	cin >> n;

	cout << solve(n) << endl;



	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;

	return 0;

}