Милі та кілометри#3188

Милі та кілометри

1 секунда
64 мегабайти
Дуже легка

Якщо ви часто подорожуєте, то могли стикатися з такою проблемою: у різних країнах використовують різні системи вимірювання. Зокрема, існують дві основні системи для вимірювання відстаней: метрична та імперська. У метричній системі використовують кілометри, а в імперській — милі. Відомо, що одна миля дорівнює приблизно кілометра. Цікаво, що це значення дуже близьке до золотого перерізу, який дорівнює приблизно . Ґрунтуючись на цьому, існує цікавий спосіб перетворювати відстані, задані в милях, у кілометри.

Розглянемо послідовність Фібоначчі: F_1 = F_2 = 1, F_n = F_{n-1} + F_{n-2} для n > 2. Відношення двох послідовних чисел Фібоначчі F_{n+1}/F_n прямує до золотого перерізу при n \to \infty. Тобто, можна представити число миль як суму чисел Фібоначчі, вибираючи найбільші можливі числа. Потім для кожного з цих чисел переходимо до наступного числа Фібоначчі і підсумовуємо нові числа. Таким чином, ви отримаєте приблизне число кілометрів.

Наприклад, 40 \to 34 + 5 + 1 \to 55 + 8 + 2 \to 65. Тобто, миль — це приблизно кілометрів (точне значення — кілометра). Напишіть програму, що реалізує цей метод.

Вхідні дані

У першому рядку вхідних даних задано число (1 \leq t \leq 10000) — кількість тестів. Далі наведено описи тестів. Кожен тест складається з одного цілого числа (1 \leq m \leq 10^{15}) — кількість миль.

Вихідні дані

Для кожного тесту виведіть приблизне число кілометрів, обчислене за методом, описаним у умові.

Приклади

Приклад 1

Loading
Loading