ADV04L  Miles and kilometers
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 1.609 kilometers. By interesting coincidence this is close enough to the value of the golden ration which is about 1.618. On this basis there is an interesting way of converting miles to kilometeres. Let's look into Fibonacci sequence: F_{1} = F_{2} = 1, F_{n} = F_{n−1} + F_{n−2}, для n > 2. The ratio of two successive Fibonacci numbers F_{n+1}/F_{n} tends to golden ration as 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, 40 ⇒ 34 + 5 + 1 ⇒ 55 + 8 + 2 ⇒ 65. That means that 40 miles is approximately 65 kilometers (more precise value is 64,37 kilometers). Write a program that implements this method.
Input
The first line of input contains number t – the amount of test cases. The description of t test cases follows. Each test consists of a single integer m  the amount of miles.
Constraints
1 <= t <= 10000
1 <= m <= 10^15
Output
For each test case output the amount of kilometers calculated using the method given in the statement.
Example
Input: 4 1 7 40 128 Output: 2 11 65 207
hide comments
Sahil Dua:
20150219 22:55:22
Nice Problem :) 

Bhavik:
20140102 18:30:40
Last edit: 20140606 20:12:54 

Hasil Sharma:
20131024 05:27:26
Nice problem :) 

Qwerty:
20130706 14:56:01
why doesnt the formula work..? 

Ouditchya Sinha:
20130526 06:53:27
@Spooky : Nicely presented problem. Thank you! :) 

The Mundane Programmer:
20130314 02:18:47
Nice problem 

Anonymous:
20130107 16:53:12
Use unsigned long long int in 'C' : This is not ANSI conformant, but gcc supports it. 

hemalatha:
20121002 10:17:29
my first dynamic programmed question....:)


Bharath Reddy:
20120707 10:05:04
for 10^15 ans = 1618033988749895 Last edit: 20120707 10:18:54 
Added by:  Spooky 
Date:  20101114 
Time limit:  0.172s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Advancement Autumn 2010, http://sevolymp.uuuq.com/ 