#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	if (n == 1) {
		cout << 1;
		return 0;
	}
	vector<long long> nums;
	nums.push_back(0);
	nums.push_back(1);
	int ans = 1;
	int i = 0;
	while (1) {
		nums.push_back(0);
		if (i >= 2) {
			nums[i] = (nums[i - 1] + nums[i - 2]) % n;
			if (nums[i - 1] == 0 && nums[i] == 1) {
				cout << ans;
				return 0;
			}
			else {
				i++;
				ans++;
			}
		}
		else {
			nums[i] = nums[i] % n;
			i++;
		}
		//cout << nums[i] << " ";
	}
	return 0;
}