Fibonacci Half Sequence

The Fibonacci sequence $f_n$ starts with 1 and 2 and is defined as follows.

• $f_1=1$
• $f_2=2$
• For $n\ge 3$, $f_n=f_{n-1}+f_{n-2}$

The half sequence $a_n$ of this Fibonacci sequence is defined as follows.

• $a_n$ is the lexicographically smallest sequence among all sequences that satisfy $a_{a_n}=f_n$ for every positive integer $n$.

Sequence $a_n$ is lexicographically smaller than $b_n$ if there exists an $i$ such that $a_j=b_j$ for every $j$ less than $i$, and $a_i<b_i$.

The first line contains the number of test cases $T$. $(1\le T\le 10\,000)$

Each of the next $T$ lines contains one value of $n$. $(1\le n\le 10^{18})$

For each $n$, print $a_n$ on its own line. If $a_n>10^{18}$, print -1 instead.