斐波那契数列 $f_n$ 定义如下：

• $f_1 = 1$
• $f_2 = 2$
• 对于 $n \ge 3$，$f_n = f_{n-1} + f_{n-2}$

该斐波那契数列的“半序列”（half-sequence），记作 $a_n$，定义如下：

• 序列 $a_n$ 是所有满足 $a_{a_n} = f_n$ 的序列中，字典序最小的序列，其中 $n$ 为所有正整数。

称序列 $a_n$ 的字典序小于 $b_n$，意味着存在某个 $i$，使得对于所有小于 $i$ 的 $j$，都有 $a_j = b_j$ 且 $a_i < b_i$。

给定一个正整数 $n$，求 $a_n$。

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 10^4$)。接下来是各测试用例。 每个测试用例由单行组成，包含一个整数 $n$ ($1 \le n \le 10^{18}$)。

输出格式

对于每个测试用例，输出 $a_n$ 的值。如果 $a_n > 10^{18}$，则输出 $-1$。

样例

样例输入 1

7
1
2
3
4
5
6
10000000

样例输出 1

1
2
3
6
13
5
-1