Description

The Answer to the Ultimate Question of Life, The Universe, and Everything. ── 42

"The Answer to the Ultimate Question of Life, The Universe, and Everything", they said.

"42", Siri said when I asked her the meaning of life.

And 42 is divided by 3.

Coincidence? I don't think so.

If we focus on the problem ID, the number is 13002, which is divided by 3.

What about the title? We seek to find the answer to "life", the "universe", and "everything". If we map 'a' as 1, 'b' as 2 and so on, the sum of "life", "universe", and "everything" is 32, 113, 133, respectively. It seems that there's no relationship between these numbers. However, if we calculate the difference of "everything" and the other two, we'll get the answer -12, which is also divided by 3. And if we resemble the title, we can even get a word "triangle".

The more we focus on, the more evidence we found. What evidence? Now I can say that this problem is:

Illuminati confirmed.

Knuckles is on his way of finding his queen. However, a strange giant triangle stele with a single eye blocked his way, Knuckles needs to solve a puzzle so that he shall pass and keep his journey of finding the queen.

---

Knuckles needs to solve the puzzle shown below:

Given a sequence $F:F_0=1,\ F_i=F_{i-1}+F_{i-2}$, and an non-negative integer $n$, he needs to find a minimal $F_1$ such that $F_x=n$ for a suitable $x$.

For example, if $n=20$, the minimal $F_1=6$ since the sequence $F$ will be $<1,6,7,13,20>$ where $F_4=n$, and we cannot find a smaller $F_1$ that $n$ appears in $F$.

Input

The input contains multiple testcases. The total number of testcases is no larger than 100.

For each testcase, there will be only one integer $n$.

$0\le n\le 10^{18}$.

Output

For each testcase, output a single number, represents the minimal non-negative integer $F_1$ that there's $n$ appears in sequence $F$.

Sample Input  Download

Sample Output  Download

Tags

Discuss