printЗадачи очного тура личного первенства

print5. Фибоначчиева система счисления

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:
`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
loading