#include using namespace std; using ll = long long; ll modPow(ll b, ll e, ll m) { ll res = 1 % m; b %= m; while(e){ if(e & 1) res = (res * b) % m; b = (b * b) % m; e >>= 1; } return res; } vector> factorize(int n){ vector> f; for (int i=2; i*i <= n; i++){ if(n % i == 0){ int cnt = 0; while(n % i == 0){ cnt++; n /= i; } f.push_back({i, cnt}); } } if(n > 1) f.push_back({n, 1}); return f; } vector divisors(int n) { vector div; for (int i = 1; i*i <= n; i++){ if(n % i == 0){ div.push_back(i); if(i * i != n) div.push_back(n / i); } } sort(div.begin(), div.end()); return div; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; if(n == 1){ cout << 1 << endl; return 0; } // φ(n) を n の素因数分解から計算 int nn = n; auto f = factorize(nn); int phi = n; for(auto &p: f) phi = phi / p.first * (p.first - 1); auto divs = divisors(phi); for(auto d : divs){ if(modPow(10, d, n) == 1){ cout << d << endl; break; } } return 0; }