ADV04L - Miles and kilometers

no tags 

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: F1 = F2 = 1, Fn = Fn−1 + Fn−2, для 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


hide comments
Sahil Dua: 2015-02-19 22:55:22

Nice Problem :)

Bhavik: 2014-01-02 18:30:40

Last edit: 2014-06-06 20:12:54
Hasil Sharma: 2013-10-24 05:27:26

Nice problem :)

Qwerty: 2013-07-06 14:56:01

why doesnt the formula work..?

Ouditchya Sinha: 2013-05-26 06:53:27

@Spooky : Nicely presented problem. Thank you! :)

The Mundane Programmer: 2013-03-14 02:18:47

Nice problem

Anonymous: 2013-01-07 16:53:12

Use unsigned long long int in 'C' : This is not ANSI conformant, but gcc supports it.

hemalatha: 2012-10-02 10:17:29

my first dynamic programmed question....:)

Bharath Reddy: 2012-07-07 10:05:04

for 10^15 ans = 1618033988749895

Last edit: 2012-07-07 10:18:54

Added by:Spooky
Date:2010-11-14
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/