Miles and kilometers#3188

Miles and kilometers

1 second
64 megabytes
Very easy

If you travel frequently, you may have encountered the following problem: different countries use different measurement systems. In particular, there are two main measurement systems for distances: metric and imperial. The metric system uses kilometers, while the imperial system uses miles. It is known that one mile is approximately kilometers. By an interesting coincidence, this value is very close to the golden ratio, which is about . Based on this, there is an interesting method to convert distances given in miles into kilometers.

Let's consider the Fibonacci sequence: F_1 = F_2 = 1, F_n = F_{n-1} + F_{n-2} for n > 2. The ratio of two consecutive Fibonacci numbers F_{n+1}/F_n approaches the golden ratio as tends to infinity. Therefore, you can partition the number of miles into a sum of Fibonacci numbers, choosing the largest possible Fibonacci numbers. Then, for each number, switch to the next Fibonacci number and sum up the new numbers. In this way, you obtain the approximate number of kilometers.

For example, 40 \to 34 + 5 + 1 \to 55 + 8 + 2 \to 65. Thus, miles is approximately kilometers (the precise value is kilometers). Write a program that implements this method.

Input

The first line of input contains the number (1 \leq t \leq 10000) — the number of test cases. This is followed by the description of test cases. Each test case consists of a single integer (1 \leq m \leq 10^{15}) — the number of miles.

Output

For each test case, output the approximate number of kilometers, calculated using the method described in the statement.

Examples

Example 1

Loading
Loading