If you are travelling a lot you could have met the following problem: different countries use different measurement systems. Notably there are two major measurement systems for distances: metric and imperial. Metric system exploits kilometers while miles are used in the imperial system. It is known that one mile is approximately \textbf{1.609} kilometers. By interesting coincidence this is close enough to the value of the golden ration which is about \textbf{1.618}. On this basis there is an interesting way of converting miles to kilometeres. Let's look into Fibonacci sequence: \textbf{F_1 = F_2 = 1}, \textbf{F_n = F_\{n-1\} + F _\{n-2\}}, for \textbf{n} > \textbf{2}. The ratio of two successive Fibonacci numbers \textbf{F_\{n+1\}/F_n} сtends to golden ration as \textit{n} tends to infinity. So you can partition the amount of miles you have into Fibonacci numbers, and you should use as large Fibonacci numbers as possible, then for each element in the partition you should go to the next Fibonacci number and sum up the elements again. That way you will get the approximate amount of kilometers. For example, \textbf{40} → \textbf{34 + 5 + 1} → \textbf{55 + 8 + 2} → \textbf{65}. That means that \textbf{40} miles is approximately \textbf{65} kilometers (more precise value is \textbf{64,37} kilometers). Write a program that implements this method. \InputFile The first line of input contains number \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10000}) - the amount of test cases. The description of \textbf{t} test cases follows. Each test consists of a single integer \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^15}) --- the amount of miles. \OutputFile For each test case output the amount of kilometers calculated using the method given in the statement.