問題文

整数 $N$ が与えられます。「整数$N$ は $k$-bonacci 数列の要素である」という主張が真となるような2以上の整数 $k$ が存在するか判定し、存在する場合は最小のものを見つけて下さい。

なお、この問題において数列 $A$ は以下の条件を全て満たすとき、また満たすときに限り、$k$-bonacci数列であると定義します。

• 　$A$ は $A_1$ を初項とし、　$A_1,A_2,A_3,\cdots$　と続く長さ無限の数列である。
• 　$i < k$　を満たすならば、$A_i = 0$　である。
• 　$i = k$　を満たすならば、$A_i = 1$　である。
• 　$i > k$　を満たすならば、$A_i = A_{i-k} + A_{i-k+1} + \cdots + A_{i-1}$　である。

入力

$N$

• 入力は全て整数
• $1 \le N \le 10^{18}$

出力

条件を満たす整数 $k$ が存在しない場合、$-1$ を出力してください。 そうでない場合、条件を満たす最小の $k$ の値を出力してください
出力は1行目に行い、最後に改行してください。

サンプル

4

3

2915

-1

518929865644420416

8