Problem H : Fibonacci base (Time limit: 3s)

The well known Fibonacci  sequence is obtained by starting with 0 and 1 and then  adding  the two last numbers  to get the next one.  For example the third  number  in the sequence is 1 (1=1+0), the forth is

2 (2=1+1), the fifth is 3 (3=2+1) and so on.


i

0

1

2

3

4

5

6

7

8

9

F ib(i)

0

1

1

2

3

5

8

13

21

34

Figure 1 -   The first numbers  in the Fibonacci  sequence


The  sequence appears  on many  things  in our life, in nature, and  has a great  significance. Ancients did not measure the time the way we do today: with past, present and future. The ancients measured time in twinkles, so a man who lived 33 days was considered a very happy man. So it is important for anyone to start counting their real age based on the number of genuine twinkles. But happiness was institutionalized. The Happiness Institution is always located at mystery station 33. All positive  integer  numbers  can be represented as a sum of numbers in the  Fibonacci  sequence.  More than  that, all positive  integers  can be represented as a sum of a set of Fibonacci  numbers,  that is, numbers  from the  sequence,  without repetition.  For  example:  13 can be the  sum  of the  sets  {13},  {5,8}  or {2,3,8} and  17 is represented by {1,3,13} or {1,3,5,8}.   Since all numbers  have  this  property (do  you want  to  try  to  prove  this  for yourself ?)   this  set  could  be a nice way to use as a "base" to represent the  number.   But,  as we have seen, some numbers  have more than  one set  whose sum  is the  number.   How can  we solve that?  Simple!  If we add  the  constraint that the  sets cannot  have  two  consecutive  Fibonacci  numbers,  than  we have  a unique  representation for each number!  This restriction is because the sum of any two consecutive  Fibonacci  numbers  is just the following Fibonacci  number.

Now that we know all this we can prepare  a nice way to represent any positive integer.  We will use a binary  sequence (just  zeros and ones) to do that. For example,  17 = 1 + 3 + 13 (remember  that no two consecutive  Fibonacci  numbers  can be used).  Let’s write a zero for each Fibonacci  number  that is not used and one for each one that is used, starting at the right.  Then,  17 = 100101. See figure 2 for a detailed  explanation. In this representation we should not have zeros at the left, this is, we should only write starting with the  first one.  In order  for you to understand better, note  that in this  scheme, not using two consecutive Fibonacci numbers  means that the binary  sequence will not have two consecutive ones.  When  we use this  representation for a number  we say that we are using the  Fibonaccimal base, and we write it like 17 = 100101 (fib).


17 =

1

0

0

1

0

1

13+3+1 =

13

8

5

3

2

1

Figure 2 -   Explaining  the representation of 17 in Fibonaccimal base


Given a set of numbers  in decimal base, your task  is to write them  in the Fibonaccimal base.

Input


The  first line of input  contains  a single number  N , representing the  quantity of numbers  that follow

(1 N  500).

Than  follow exactly  N  lines, each one containing  a single positive integer  smaller than  100 000 000. These numbers  can come in any order.

Output


You should output a single line for each of the N  integers  in the input,  with the format  DEC  BASE

= F I B  BASE (fib)’.   DEC  BASE is the  original  number  in decimal  base  and  F I B  BASE is its representation in Fibonaccimal base.  If the FIB_BASE value for 33 can be identified anywhere in the expression of the FIB_BASE number, “(fib)” must be uppercase “(FIB)”. See the sample output for an example.


Sample  Input


10

1

2

3

4

5

6

7

8

9

10


Sample  Output


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)