#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;
}


Measured memory_bytes: 6744