#include using namespace std; using ll = long long; using str = string; #define re(n) for(int _=0;_=0; i--) #define per1(i,s,n) for(int i=int(n)-1; i>=s; i--) #define all(x) x.begin(), x.end() #define SORT(v) sort(all(v)) #define REV(v) reverse(all(v)) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define elif else if #define len(x) ll(x.size()) #define _GLIBCXX_DEBUG template inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } templatevoid vcin(vector &n){for(int i=0;i>n[i];} templatevoid vcout(vector &n){for(int i=0;i; using vvi = vector; using pii = pair; using vl = vector; using vvl = vector; using pll = pair; using vpi = vector; using vpl = vector; using vc = vector; using vs = vector; using quei = deque; using quel = deque; #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") int main() { int n; cin >> n; if (n == 9 || n == 1 || n == 3){ cout << 1 << endl; return 0; } ll tmp = 9; rep(i,2*n+100) { tmp *= 10; tmp += 9; tmp %= n; if (tmp == 0) { cout << i + 2 << endl; return 0; } } return 0; }