Problem Statement

You are given an integer $N$. Determine whether there exists an integer $k$ greater than or equal to 2 for which the claim "the integer $N$ is an element of the $k$-bonacci sequence" is true, and if one exists, find the smallest such value.

In this problem, a sequence $A$ is defined to be a $k$-bonacci sequence if and only if it satisfies all of the following conditions.

• 　$A$ is an infinite sequence with first term $A_1$, continuing as　$A_1,A_2,A_3,\cdots$.
• 　If　$i < k$　holds, then　$A_i = 0$.
• 　If　$i = k$　holds, then　$A_i = 1$.
• 　If　$i > k$　holds, then　$A_i = A_{i-k} + A_{i-k+1} + \cdots + A_{i-1}$.

Input

$N$

• All inputs are integers.
• $1 \le N \le 10^{18}$

Output

If no integer $k$ satisfying the condition exists, print $-1$. Otherwise, print the smallest value of $k$ satisfying the condition.
Print the output on the first line, followed by a newline at the end.

Sample

4

3

2915

-1

518929865644420416

8