948 - Fibonaccimal Base

著名的費氏數列(Fibonacci sequence) 的前兩項為 0 與 1，之後的每一項為其前兩項的和，例如第三項為第一、二項的和(1=0+1)，第四項為第二、三項之和(3=1+2)。

i	0	1	2	3	4	5	6	7	8	9
Fib(i)	0	1	1	2	3	5	8	13	21	34

Figure 1 - 費氏數列前十項

在現實世界中不難發現費氏數列的縱跡，它有其重要的地位。另外，你可知所有正整數都可以用費氏數列中取部份項的和來表示嗎？說的再更精確一點：所有正整數都可以用費氏數列中取部份"不重複"的項來表示。例如，13可以下列不同的組合來表示{13}，或{5, 8}，或{2, 3, 8}，而17則可用{1, 3, 13}或{1, 3, 5, 8}來表示。由於所有正整數都可以用不重複的費氏數列的項次來表示，所以就可以把費氏數列的項次當作是"基底"(base)來編織出所有的正整數。但是由上面的列子可知其表示式可能不只一種，解決之道很簡單，就是規定任兩個被選中的項次不能在數列中相鄰，如此可保證所有正整數都只有唯一一組表示方式，這種限制規定是基於任兩個相鄰的項的和就等於下一個項次。

 現在我們已知任一正整數的這種費式數列基底表示法，我們以17為例來說明，17=1+3+13，表示17要取三項：1的項、3的項、13的項，而不取2的項、4的項、5的項及其他項。所以17=100101，如下圖：

17 =	1	0	0	1	0	1
13+3+1 =	13	8	5	3	2	1

Figure 2 - 17的費式數列基底表示法

The Problem

給你一個以十進位為基底的值，請你寫出該值以費式數列為基底的表示式。

Input

第一列有一個整數N表示測試資料的組數，1 <= N <= 500。接下來有N列，每一列有一正整數，其值小於100,000,000。

Output

請以下列的格式輸出答案。

Example Input

10
1
2
3
4
5
6
7
8
9
10

Example 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)

---

原文出處