## FIBPOS - Fibonacci Terms

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}= 1 - F
_{2}= 1 - F
_{i}= F_{i-1}+ F_{i-2}for each i > 2
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
_{2}= 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})
FP(1)=2 (first rule) FP(5)=5 (second rule F _{5} = 5) FP(4)=4.5 (third rule, is right in the middle of F _{4} = 3 and F_{5} = 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 <= 10 ^{8}**.

### 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 |