Description

It is known that any positive integer can be decomposed into several Fibonacci numbers. Now, you are asked to find a decomposition of $n$.

Input Format

The first line contains an integer $t$, the number of test cases.

Then follow $t$ lines, each containing an integer $n$ (as described).

Output Format

Output $t$ lines. Each line contains a string representing a decomposition in the format $n = a_1 + a_2 + a_3 + \ldots + a_k$, and the summands must be listed from small to large.

1
1

1=1

1
10

10=2+8

Hint

If there are multiple valid decompositions, choose the one with the fewest summands. If there is still more than one, output the one whose rightmost summands are as large as possible.

For $100\%$ of the testdata, $t \leq 1000$, $1 \leq n \leq 10^{9}$.

Translated by ChatGPT 5