Рабочее место участника

Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:

`F_0=0`, `F_1=1`, `F_n=F_{n-1}+F_{n-2}` для `n>1`.

Фибоначчиева система счисления (ФСС) основана на теореме Цеккендорфа, утверждающей, что любое целое положительное число имеет единственное представление вида

`N=F_{k_1}+F_{k_2}+…+F_{k_r}`, где `F_{k_i}` – число Фибоначчи, а `k_1\ ">>"\ k_2\ ">>"\ …\ ">>"\ k_r\ ">>"\ 0`.

Здесь `i\ ">>"\ j` означает, что `i\ ≥\ j+2`. Целое неотрицательное число можно записать в виде последовательности нулей и единиц:

`N=(b_m\ b_{m-1}…b_2)_F\ hArr\ N\ =\ sum_{i=2}^m\ b_i*F_i`, где `b_i\ =\ 1`, если `F_i` входит в преставление, иначе 0.

Например, `1000000` = `832040\ +\ 121393\ +\ 46368\ +\ 144\ +\ 55` = `F_30\ +\ F_26\ +\ F_24\ +\ F_12\ +\ F_10` или `(1000000)_10\ =\ (10001010000000000010100000000)_F`. Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются две 1 подряд.

Напишите программу, которая вводит числа в десятичной системе счисления и выводит их в ФСС.

Во входном файле в первой строке содержится число `T` (`0\ <\ T\ <\ 100`) – количество тестов. Каждый тест распологается на своей строке, он состоит из одного числа `N` (`0\ <\ N\ <\ 10^100`), записанного в десятичной системе счисления.

В выходной файл для каждого введенного числа вывести его представление в Фибоначчиевой системе счисления. Число обязательно должно начинаться с 1.

3
1
100
1000

1
1000010100
100000000100000