The Fibonacci sequence is a sequence of integers in which each number is equal to the sum of the two preceding numbers. The first two integers in the sequence are both 1. Formally:

• F₁ = 1
• F₂ = 1
• F_i = F_i-1 + F_i-2 for each i > 2

The beginning of this sequence is 1, 1, 2, 3, 5, 8, 13, 21.

We'll define the Fibonacci position of an integer greater than or equal to 1 as follows:

• The Fibonacci position of 1 is 2 (since F₂ = 1)
• The Fibonacci position of any integer n > 1 such that F_i = n is i
• The Fibonacci position of any integer n > 1 such that it is strictly between F_i and F_i+1 is i+(n-F_i)/(F_i+1-F_i) (informally, this means it is linearly distributed between F_i and F_i+1)

As examples, if FP(n) is the Fibonacci position of n,

• FP(1) = 2 (first rule)
• FP(5) = 5 (second rule F₅ = 5)
• FP(4) = 4.5 (third rule, is right in the middle of F₄ = 3 and F₅ = 5)

Given an integer n, find its Fibonacci position as a double.

Input

First line contains T <= 10. The following N lines each contain an integer 1 <= n <= 10⁸.

Output

For each test case, print the Fibonacci position of n, rounded to 6 places of decimal.

Example

Input:
4
1
5
4
100

Output:
2.000000
5.000000
4.500000
11.200000