## 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:
4154100 Output:
2.0000005.0000004.50000011.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