Фибоначчиева система счисления
Как известно, последовательность Фибоначчи начинается с двух чисел 0 и 1 и каждый последующий член последовательности получается как сумма двух предыдущих. Например, третий член последовательности это 1 (1=1+0), четвёртый - 2 (2=1+1), пятый - 3 (3=2+1) и т.д.
Рисунок 1 - Первые числа последовательности Фибоначчи
Эта последовательность проявляется очень часто и в нашей жизни и в природе и имеет большое значение. А знаете ли Вы, что все положительные целые числа можно представить как сумму чисел из последовательности Фибоначчи? Более того, все натуральные числа можно представить при помощи последовательности Фибоначчи, причём без повторений. Например: 13 может быть представлено из указанного множества как {13}, {5,8} или {2,3,8} а 17 представлено как {1,3,13} или {1,3,5,8}. Так как все числа обладают этим свойством (может у Вас есть желание доказать это?), то этот набор является хорошим способом для использования в качестве "базы" (основания системы счисления) для представления чисел. Но, как мы видели выше, некоторые числа могут быть представлены более чем одним способом суммой чисел из последовательности Фибоначчи. Как нам выйти из этой ситуации? Очень просто! Для этого достаточно наложить ограничение, что для предоставления числа нельзя использовать два соседних элемента из последовательности Фибоначчи! Это ограничение объясняется тем, что сумма двух соседних членов последовательности Фибоначчи сама является членом последовательности Фибоначчи.
Теперь, когда мы знаем всё изложенное выше, мы можем предложить хороший способ предоставления любого целого положительного числа. Для этого мы будем использовать двоичную последовательность (только нулей и единиц). Например, 17 = 1 + 3 + 13 (мы должны помнить, что нельзя использовать два последовательных числа Фибоначчи). Будем использовать ноль в записи, если очередное число из последовательности Фибоначчи не используется, и единицу для тех что используются. Тогда, 17 = 100101 (ведущие нули должны быть опущены). На рисунке 2 подробно показано, как получена эта запись и что означают нули и единицы в приведённой выше записи. Для лучшего понимания этой схемы обратим внимание на тот факт, что не использование двух соседних чисел Фибоначчи означает, что двоичная последовательность не будет иметь двух подряд идущих единиц. Используя приведённое представление числа, мы будем говорить, что мы используем Фибоначчиеву систему счисления и записывать его как 17 = 100101 (fib).
Рисунок 2 - Объяснение представления числа 17 в Фибоначчиевой системе счисления
Ваша задача состоит в записи заднного десятичного числа в Фибоначчиевой системе счисления.
Входные данные
В первой строке входных данных задано единственное натуральное число N, указывающее на количество примеров в тесте (1 ≤ N ≤ 500).
Следующие N строк содержат по одному положительному целому числу, не превышающему 100 000 000. Числа могут быть поданы в произвольном порядке.
Выходные данные
Вы должны вывести по одной строке для каждого из N чисел, полученных во входных данных, в следующем формате: "DEC_BASE = FIB_BASE (fib)". DEC_BASE это заданное оригинальное число в десятичной системе счисления, а FIB_BASE соответственно - его представление в Фибоначчиевой системе счисления. Образец вывода приведён в примере выходных данных.