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⁵
• 1≤ N ≤ 10¹⁵

Scoring:

• 1 ≤ T ≤ 10⁵,1 ≤ N ≤ 10⁵ : ( 30 pts )
• 1 ≤ T ≤ 10⁵,1 ≤ N ≤ 10⁹ : ( 30 pts )
• 1 ≤ T ≤ 10⁵,1 ≤ N ≤ 10¹⁵ : ( 40 pts )