#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;
    vector<long long> f(1000000);
    f[1] = 1LL % n;
    f[2] = 1LL % n;
    for (int i = 3; i < 1000000; i++) {
        f[i] = (f[i - 2] + f[i - 1]) % n;
    }
    for (int i = 1; i < 1000000; i++) {
        if (f[i] == 0) {
            cout << i << endl;
            return 0;
        }
    }
}