Мили и километры
Если вы часто путешествуете, вы могли столкнуться со следующей проблемой: в различных странах используют различные системы измерения. В частности существуют две основные системы измерения расстояния: метрическая и английская. В метрической системе используются километры, а в английской - мили. Известно, что в одной миле примерно 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 стремящемся к бесконечности. Поэтому можно количество миль разбить на сумму чисел Фибоначчи, причем надо выбирать как можно большие числа Фибоначчи, затем для каждого числа перейти к следующему числу Фибоначчи и снова просуммировать. Таким образом, мы получим приближенное количество километров. Например, 40 → 34 + 5 + 1 → 55 + 8 + 2 → 65. Значит 40 миль примерно равно 65 километров (точное значение 64,37 километра). Напишите программу, которая реализует этот метод.
Входные данные
Первая строка входа содержит число t (1 ≤ t ≤ 10000) - количество тестов. Далее идет описание t тестов. Каждый тест состоит из единственного целого числа m (1 ≤ m ≤ 10^15) — количества миль.
Выходные данные
Для каждого теста выведите примерное количество километров, посчитанное описанным в условии методом.