Fibonaccimal Base#1378
The well-known Fibonacci sequence is obtained by starting with and , and each next number is the sum of the previous two. For example, the third number in the sequence is (1 = 1 + 0), the fourth is (2 = 1 + 1), the fifth is (3 = 2 + 1), and so on.
Figure 1 - The first numbers in the Fibonacci sequence
This sequence appears frequently in nature and daily life, and has great significance. Did you know that every positive integer can be represented as a sum of numbers from the Fibonacci sequence? More than that, every positive integer can be written as a sum of Fibonacci numbers (from the sequence), with no repetitions. For example, can be represented as , , or \{2, 3, 8\}, and can be represented as \{1, 3, 13\} or \{1, 3, 5, 8\}. Since all numbers have this property (you can try to prove this), this set can be used as a "base" to represent numbers. However, as seen above, some numbers can be represented by more than one such set. How do we resolve this? It's simple! If we add the constraint that no two consecutive Fibonacci numbers may appear in the representation, then each number has a unique representation. This restriction exists because the sum of any two consecutive Fibonacci numbers is equal to the next Fibonacci number.
With this knowledge, we can construct a good way to represent any positive integer. We will use a binary sequence (only zeros and ones) for this. For example, 17 = 1 + 3 + 13 (without using two consecutive Fibonacci numbers). We write a zero if a Fibonacci number is not used, and one if it is used, starting from the right. Thus, 17 = 100101 (there must not be leading zeros). Figure 2 explains this representation in detail. In this scheme, not using two consecutive Fibonacci numbers means the binary sequence will not have two consecutive ones. Using this representation, we say we are using the Fibonaccimal base, and write 17 = 100101 (fib).
Figure 2 - Explaining the representation of in Fibonaccimal base
Given a decimal number, your task is to write it in the Fibonaccimal base.
The first line contains a single natural number (1 \leq N \leq 500), the number of test cases.
The next lines contain a single positive integer not exceeding each. The numbers can be given in any order.
For each of the numbers, output one line in the format "DEC_BASE = FIB_BASE (fib)". DEC_BASE is the original number in decimal, and FIB_BASE is its representation in the Fibonaccimal base. See the sample output for an example.
Example 1