N = gets.to_i

(1 .. 800).each do |m|
	a, b = 0, 1
	if (0 ... m * 2).all? { |i| c = (a % N == 0) == (i % m == 0); a, b = b, (a + b) % N; c }
		puts m
		exit
	end
end