28404번 - 피보나치 반반수열

문제

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을 대신 출력한다.

제한

힌트