Semi-Fibonacci

   Time limit:   1 second

   Memory limit: 64 megabytes

A sequence {an} is defined as follows:

(|
|{a1 = 1
|a2n = an
|(a     = a   + a
  2n+1     2n    2n-1

You are given a positive integer m, and asked to answer whether m appears in {an} or not. If yes, try to find the minimal n that an = m.

Input

The input contains several test cases, the number of test cases is up to 1 000.

For each test case, only one line contains a positive integer m as mentioned above, where m < 1018.

Output

For each test case, output a line containing an integer indicating the answer to this question. If m is in the sequence, then output the minimal n that an = m. Otherwise, output -1.

We guarantee that the output is within the range of long long, if the given m is in sequence {an}.

Sample Input

1

2

7

Sample Output

1

3

-1