Seeing the fame received by the Fibonacci numbers, the other Natural Numbers were feeling jealous. Therefore, to give them their shot at glory Mr. Non-Fibo now wants you to tell him the N^th- Non Fibonacci Number.
Input:
First line contains T which is the number of test cases.
T lines follow each with an integer N.

Output:
For each N output the Nth Non-Fibonacci number.

Constraints:

1 ≤ T ≤ 10^5
1≤ N ≤ 10^15

Scoring:

1 ≤ T ≤ 10^5,1 ≤ N ≤ 10^5 : ( 30 pts )
1 ≤ T ≤ 10^5,1 ≤ N ≤ 10^9 : ( 30 pts )
1 ≤ T ≤ 10^5,1 ≤ N ≤ 10^15 : ( 40 pts )

SAMPLE INPUT
3
1
2
3

SAMPLE OUTPUT
4
6
7

Explanation

The first few Natural Numbers that are Fibonacci are : 1,2,3,5,8,13..
Thus the first few Natural Numbers that are not Fibonacci are 4,6,7,9,...

见题面

见题面