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 kilometers. Let's look into Fibonacci sequence: F1 = F2 = 1, Fn = Fn−1 + Fn−2, for n > 2. The ratio of two successive Fibonacci numbers Fn+1/Fn 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

Added by:Spooky
Date:2010-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Advancement Autumn 2010, http://sevolymp.uuuq.com/

hide comments
2022-01-07 18:28:02
Nice problem!
2015-02-19 22:55:22 Sahil Dua
Nice Problem :)
2013-10-24 05:27:26 Hasil Sharma
Nice problem :)
2013-07-06 14:56:01 Qwerty
why doesnt the formula work..?
2013-05-26 06:53:27 Ouditchya Sinha
@Spooky : Nicely presented problem. Thank you! :)
2013-03-14 02:18:47 The Mundane Programmer
Nice problem
2013-01-07 16:53:12 Anonymous
Use unsigned long long int in 'C' : This is not ANSI conformant, but gcc supports it.
2012-10-02 10:17:29 hemalatha
my first dynamic programmed question....:)
2012-07-07 10:05:04 Bharath Reddy
for 10^15 ans = 1618033988749895

Last edit: 2012-07-07 10:18:54
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.