{"raw_statement":[{"iden":"problem statement","content":"You are given a positive integer $N$.  \nOutput one pair of non-negative integer sequences $P=(P_1, P_2, \\dots,P_N), A=(A_1, A_2, \\dots,A_N)$ that satisfies all of the following conditions:\n\n*   $0 \\leq P_i < 2^{30}~(1 \\leq i \\leq N)$\n*   $0 \\leq A_i < 2^{30}~(1 \\leq i \\leq N)$\n*   The length of a longest strictly increasing subsequence of $(P_1~\\mathrm{OR}~A_i, P_2~\\mathrm{OR}~A_i, \\dots, P_N~\\mathrm{OR}~A_i)$ is $i$. $(1 \\leq i \\leq N)$\n    *   $\\mathrm{OR}$ denotes the bitwise $\\mathrm{OR}$ operation.\n\nIt can be proved that under the constraints of this problem, there exists at least one pair $P, A$ that satisfies the conditions.\nSolve $T$ test cases per input.\nWhat is bitwise $\\mathrm{OR}$?The bitwise $\\mathrm{OR}$ of non-negative integers $A, B$, denoted $A\\ \\mathrm{OR}\\ B$, is defined as follows:\n\n*   When $A\\ \\mathrm{OR}\\ B$ is written in binary, the digit at position $2^k$ ($k \\geq 0$) is $1$ if at least one of the digits at position $2^k$ in the binary representations of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor example, $3\\ \\mathrm{OR}\\ 5 = 7$ (in binary: $011\\ \\mathrm{OR}\\ 101 = 111$)."},{"iden":"constraints","content":"*   $1 \\leq T$\n*   $1 \\leq N \\leq 1024$\n*   For test cases in a single input, the sum of $N$ is at most $200000$.\n*   For test cases in a single input, the sum of $N^2$ is at most $1024^2$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$"},{"iden":"sample input 1","content":"3\n3\n8\n1"},{"iden":"sample output 1","content":"3 14 5\n13 2 10\n6 902 909 186 684 219 471 248\n1023 249 64 0 264 768 778 794\n2025\n1026\n\nFor the first test case, the sample output is $P = (3, 14, 5), A = (13, 2, 10)$.\n\n*   One longest strictly increasing subsequence of $(3~\\mathrm{OR}~13, 14~\\mathrm{OR}~13, 5~\\mathrm{OR}~13) = (15, 15, 13)$ is $(13)$, whose length is $1$.\n*   One longest strictly increasing subsequence of $(3~\\mathrm{OR}~2, 14~\\mathrm{OR}~2, 5~\\mathrm{OR}~2) = (3, 14, 7)$ is $(3, 7)$, whose length is $2$.\n*   One longest strictly increasing subsequence of $(3~\\mathrm{OR}~10, 14~\\mathrm{OR}~10, 5~\\mathrm{OR}~10) = (11, 14, 15)$ is $(11, 14, 15)$, whose length is $3$.\n\nFrom the above, it can be confirmed that $P = (3, 14, 5), A = (13, 2, 10)$ satisfies the conditions."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}