FIBPOS - Fibonacci Terms

no tags 


  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:
  • F1 = 1
  • F2 = 1
  • Fi = Fi-1 + Fi-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 F2 = 1)
  • The fibonacci position of any integer n > 1 such that Fi = n is i
  • The fibonacci position of any integer n > 1 such that it is strictly between Fi and Fi+1 is i+(n-Fi)/(Fi+1-Fi) (informally, this means it is linearly distributed between Fi and Fi+1)
As examples, if FP(n) is the fibonacci position of n,

FP(1)=2 (first rule)

FP(5)=5 (second rule F5 = 5)

FP(4)=4.5 (third rule, is right in the middle of F4 = 3 and F5 = 5)

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

Input

First line contains T <= 10. Following each line contains an integer 1 <= n <= 108.

Output

For each testcase, 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


Added by:Mahesh Chandra Sharma
Date:2011-01-28
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64