Largest Prime Fibonacci Number

Given an integer \(n\), your task is to find the largest prime number that is also a Fibonacci number and is less than or equal to \(n\). If no such number exists, output \(-1\).

The Fibonacci sequence is defined as follows:

\(F_0 = 0,\quad F_1 = 1,\quad F_{k} = F_{k-1} + F_{k-2}\) for \(k \ge 2\).

An integer \(p\) is prime if it is greater than 1 and has no positive divisors other than 1 and itself.

Input is read from standard input and output is written to standard output.

inputFormat

The input consists of a single integer \(n\) (\(1 \le n \le 10^9\)) given in the standard input.

outputFormat

Output the largest prime Fibonacci number less than or equal to \(n\). If no such number exists, output \(-1\).

10

5