피보나치 반반수열

$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$라는 것을 의미한다.

양의 정수 $n$이 주어졌을 때, $a\_n$을 구하시오.

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

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

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