{"raw_statement":[{"iden":"statement","content":"On Planet E, people counts in base $phi.alt$!\n\nWe are all familiar with decimal representations. In decimal representation, each digit $x_i$ satisfies $0 <= x_i <= 9$ and $overline(x_q x_{q -1} x_{q -2} \\\\dots x_0. x_{-1} x_{-2} \\\\dots x_p)$ represents $$ \\sum_{i = p}^q x_i 10^i = x_q 10^q + x_{q - 1} 10^{q - 1} + \\ldots + x_p 10^p. $$\n\nThis can be naturally extended to any integer base $b >= 2$. In base $b$, each digit $x_i$ satisfies $0 <= x_i <= b -1$ and $overline(x_q x_(q -1) x_(q -2) \\\\dots x_0. x_(-1) x_(-2) \\\\dots x_p)$ represents $$ \\sum_{i = p}^q x_i b^i = x_q b^q + x_{q - 1} b^{q - 1} + \\ldots + x_p b^p. $$\n\nNow it comes to non-integral bases! Let $phi.alt = (1 + sqrt(5)) \\/ 2$ be the golden ratio. It can be shown that every positive integer $n$ can be represented in $$ n = \\sum_{i = p}^q x_i \\phi^i = x_q \\phi^q + x_{q - 1} \\phi^{q - 1} + \\ldots + x_p \\phi^p, $$ where each digit $x_i$ is either $0$ or $1$, and any adjacent digits $x_i$ and $x_(i + 1)$ are not both $1$. This representation is unique and is called the base $phi.alt$ representation.\n\nCan you help the people on Planet E to convert a positive number in base $phi.alt$?\n\nThe first line contains a positive integer $T$ ($T <= 10$), the number of testcases.\n\nEach testcase contains a positive integer $n$ ($n <= 100000$).\n\nFor each testcase, output a single line consisting of the representation of $n$ in base $phi.alt$.\n\n"},{"iden":"input","content":"The first line contains a positive integer $T$ ($T <= 10$), the number of testcases.Each testcase contains a positive integer $n$ ($n <= 100000$)."},{"iden":"output","content":"For each testcase, output a single line consisting of the representation of $n$ in base $phi.alt$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $\\phi = \\frac{1 + \\sqrt{5}}{2}$ be the golden ratio.  \nLet $T \\in \\mathbb{Z}^+$ be the number of test cases.  \nFor each test case $k \\in \\{1, \\dots, T\\}$, let $n_k \\in \\mathbb{Z}^+$ be the input integer.\n\n**Constraints**  \n1. $1 \\le T \\le 10$  \n2. $1 \\le n_k \\le 100000$ for all $k \\in \\{1, \\dots, T\\}$\n\n**Objective**  \nFor each $n_k$, find the unique representation  \n$$\nn_k = \\sum_{i = p}^q x_i \\phi^i\n$$  \nwhere $x_i \\in \\{0, 1\\}$ for all $i$, and $x_i \\cdot x_{i+1} = 0$ for all $i$ (no two adjacent digits are 1).  \nOutput the digit sequence $x_q x_{q-1} \\dots x_p$ in order of decreasing $i$.","simple_statement":"Given a positive integer n, find its unique base φ representation, where φ = (1+√5)/2, using only digits 0 and 1, with no two adjacent 1s.","has_page_source":false}