Problem Description

Score: $ 300 $ points

penguinman fell in love with Fibonaccyan.

Knowing that Fibonaccyan likes a certain positive integer $ P $, penguinman decided to find the smallest positive integer $ i $ such that $ F_i $ is divisible by $ P $ and present it to her. Here, $ F $ is a sequence defined by the following recurrence relation:

• $ F_1=F_2=1 $
• $F_{i+2}=F_{i+1}+F_i\ (1\leq\ i)$

Help penguinman find such an integer $ i $ or inform him if no such $ i $ exists.

Input Format

The input is given from the standard input in the following format:

$ P $

Output Format

If no integer $ i $ satisfies the conditions in the problem statement, output $ -1 $.

If such an $ i $ exists, output $ i $.

Do not forget to add a newline at the end of the output.

Sample Input and Output

Sample Input #1

3

Sample Output #1

4

Sample Input #2

10

Sample Output #2

15

Sample Input #3

3000

Sample Output #3

1500

Notes/Hints

None

见题面 Input 部分

见题面 Output 部分