Elias Omega Coding

Elias codes are prefix codes for encoding positive integers efficiently when nothing is known in advance about how large the integers will be, and when a smaller integer is assumed to be at least as likely as a larger one. For this problem we bound the magnitude of the integers, and every integer to encode is greater than $1$.

Elias defined three variants — Elias gamma, Elias delta, and Elias omega. This problem introduces the gamma and omega variants and asks you to implement the Elias omega code.

Let $\beta(n)$ denote the binary representation of a positive integer $n$ (its leading bit is always $1$), and let $|\beta(n)|$ be its number of bits. If a receiver already knew $|\beta(n)|$, the sender could transmit $\beta(n)$ alone. When the receiver does not know it, the length must first be sent in a self-delimiting way; the variants differ in how that length is encoded.

Elias gamma. A positive integer $n$ is written as two concatenated fields: a prefix of $\lfloor \log_2 n \rfloor$ zero bits, followed by $\beta(n)$, which occupies $\lfloor \log_2 n \rfloor + 1$ bits. For example $\beta(9) = 1001$, so the gamma code of $9$ is $0001001$: the three leading zeros announce that four bits follow, and those four bits are $\beta(9)$.

Elias omega. Instead of a plain run of leading zeros, the omega code encodes the length recursively. Writing $\lfloor \log_2 n \rfloor = |\beta(n)| - 1$, the omega code is defined by

$\mathrm{code}(n) = \begin{cases} 0\,\beta(n), & \text{if } \lfloor \log_2 n \rfloor = 1, \\ \mathrm{code}\!\left(\lfloor \log_2 n \rfloor\right)\,\beta(n), & \text{otherwise.} \end{cases}$

In other words, the recursion stops as soon as a stage needs only a single leading $0$.

As an illustration, take $536870907$, whose binary form $\beta(536870907)$ needs $29$ bits. Building the code stage by stage (with $\beta(2)=10$, $\beta(4)=100$, $\beta(28)=11100$):

$0 \;\; 10 \;\; 100 \;\; 11100 \;\; \beta(536870907).$

Concatenating everything yields the Elias omega code

$0101001110011111111111111111111111111011,$

which can be uniquely decoded back to $536870907$.

Given several positive integers, output the Elias omega code of each.

Each line contains one positive integer $n$ with $2 \le n \le 2{,}000{,}000{,}000$. A line containing $0$ marks the end of the input and is not encoded. At most $100$ integers are given before the terminating $0$.

For each integer of the input (excluding the terminating $0$), print its Elias omega code on its own line, in the same order. The output must contain no spaces and no blank lines.