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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    if(N == 1){
        cout << 1 << '\n';
        return 0;
    }
    int a = 1 % N, b = 1 % N;
    for(int i = 3; i <= N * N; i++){
        int c = (a + b) % N;
        if(c == 0){
            cout << i << '\n';
            return 0;
        }
        a = b, b = c;
    }
}