#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 1<<30;
const long long INFLL = 1LL<<60;
const int MOD = 998244353;

int n;

int main() {
    cin >> n;
    
    int x = 0, y = 1;
    int m;
    for (int i=1; i < 1000; i++){
        if (y % n == 0){
            m = i;
            break;
        }
        y = (y + x) % n;
        x = (y - x) % n;
    }
    cout << m << endl;
    return 0;
}