eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Мили и километры

Мили и километры

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Если вы часто путешествуете, вы могли столкнуться со следующей проблемой: в различных странах используют различные системы измерения. В частности существуют две основные системы измерения расстояния: метрическая и английская. В метрической системе используются километры, а в английской - мили. Известно, что в одной миле примерно 1,609 километров. По интересному совпадению это очень близко к значению золотого сечения 1,618. Исходя из этого, существует интересный способ перевода расстояния, записанного в милях, в километры. Рассмотрим последовательность Фибоначчи: F_1 = F_2 = 1, F_n = F_{n-1} + F _{n-2}, для n > 2. Отношение двух последовательных чисел Фибоначчи F_{n+1}/F_n стремится к значению золотого сечения при n стремящемся к бесконечности. Поэтому можно количество миль разбить на сумму чисел Фибоначчи, причем надо выбирать как можно большие числа Фибоначчи, затем для каждого числа перейти к следующему числу Фибоначчи и снова просуммировать. Таким образом, мы получим приближенное количество километров. Например, 4034 + 5 + 155 + 8 + 265. Значит 40 миль примерно равно 65 километров (точное значение 64,37 километра). Напишите программу, которая реализует этот метод.

Входные данные

Первая строка входа содержит число t (1t10000) - количество тестов. Далее идет описание t тестов. Каждый тест состоит из единственного целого числа m (1m10^15) — количества миль.

Выходные данные

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

Пример

Входные данные #1
4
1
7
40
128
Выходные данные #1
2
11
65
207