피보나치 반반수열

1, 2로 시작하는 피보나치 수열 $f_n$은 다음과 같이 정의한다.

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

이 피보나치 수열의 반반수열 $a_n$은 다음과 같이 정의한다.

• $a_n$은 모든 양의 정수 $n$에 대해 $a_{a_n}=f_n$을 만족하는 모든 수열 중에서 사전 순으로 가장 작은 수열이다.

수열 $a_n$이 $b_n$보다 사전 순으로 작다는 것은, 어떤 $i$가 존재하여 $i$보다 작은 모든 $j$에 대해 $a_j=b_j$이고 $a_i<b_i$인 것을 뜻한다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 10\,000)$

다음 줄부터 $T$개의 줄에 걸쳐 $n$의 값이 한 줄에 하나씩 주어진다. $(1\le n\le 10^{18})$

$T$개의 줄에 걸쳐 각각의 $n$에 대해 $a_n$의 값을 출력한다. $a_n>10^{18}$이라면 -1을 대신 출력한다.