eolymp
Задачі

Фібоначчієва система числення

Фібоначчієва система числення

Як відомо, послідовність Фібоначчі починається з двох чисел 0 та 1 і кожен наступний член послідовності отримується як сума двох попередніх. Наприклад, третій член послідовності це 1 (1=1+0), четвертий - 2 (2=1+1), п'ятий - 3 (3=2+1) і т.д.

i0123456789
Fib(i)0112358132134

Рисунок 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).

17=100101
13+3+1=1385321

Рисунок 2 - Пояснення подання числа 17 у Фібоначчієвій системі числення

Ваша задача полягає у запису задного десяткового числаув Фібоначчієвій системі числення.

Вхідні дані

У першому рядку вхідних даних задано єдине натуральне число N, яке вказує на кількість прикладів у тесті (1N500).

Наступні N рядків містять по одному додатньому цілому числу, яке не перевищує 100 000 000. Числа можуть бути подані у довільному порядку.

Вихідні дані

Ви повинні вивести по одному рядку для кожного з N чисел, отриманих у вхідних даних, у наступному форматі: "DEC_BASE = FIB_BASE (fib)". DEC_BASE це задане оригінальне число у десятковій системі числення, а FIB_BASE відповідно - його подання у Фібоначчієвій системі числення. Зразок виведення наведено у прикладі вихідних даних.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
10
1
2
3
4
5
6
7
8
9
10
Вихідні дані #1
1 = 1 (fib)
2 = 10 (fib)
3 = 100 (fib)
4 = 101 (fib)
5 = 1000 (fib)
6 = 1001 (fib)
7 = 1010 (fib)
8 = 10000 (fib)
9 = 10001 (fib)
10 = 10010 (fib)