Задачі
Милі та кілометри
Милі та кілометри
Якщо ви часто подорожуєте, ви могли зіткнутись з наступною проблемою: у різних країнах використовуються різні системи вимірювання. Зокрема існує дві основні системи вимірювання відстані: метрична та англійська. У метричній системі використовуються кілометри, а у англійській - милі. Відомо, що в одній милі приблизно \textbf{1,609} кілометрів. За цікавим співпадінням це дуже близько до значення золотого перетину \textbf{1,618}. Виходячи з цього, існує цікавий спосіб переводення відстані, записаної в милях, у кілометри. Розглянемо послідовність Фібоначчі: \textbf{F_1 = F_2 = 1}, \textbf{F_n = F_\{n-1\} + F _\{n-2\}}, для \textbf{n} > \textbf{2}. Відношення двох послідовних чисел Фібоначчі \textbf{F_\{n+1\}/F_n} прямує до значення золотого перетину при \textbf{n} яке прямує до нескінченності. Тому можна кількість миль розбити на суму чисел Фібоначчі, причому потрібно вибирати якомога більші числа Фібоначчі, потім для кожного числа перейти до наступного числа Фібоначчі і знову просумувати. Таким чином, ми отримаємо наближену кількість кілометрів. Наприклад, \textbf{40} → \textbf{34 + 5 + 1} → \textbf{55 + 8 + 2} → \textbf{65}. Значить \textbf{40} миль прибдизно дорівнює \textbf{65} кілометрів (точне значення \textbf{64,37} кілометри). Напишіть програму, яка реалізує цей метод.
\InputFile
Перший рядок входу містить число \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10000}) - кількість тестів. Далі йде опис \textbf{t} тестів. Кожен тест складається з єдиного цілого числа \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^15}) --- кількості миль.
\OutputFile
Для кожного тесту виведіть приблизну кількість кілометрів, пораховану описаним в умові методом.
Вхідні дані #1
4 1 7 40 128
Вихідні дані #1
2 11 65 207