{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eYou are given a complete graph with N vertices, numbered from 1 to N. \u003cbr\u003eThe weight of the edge between vertex x and vertex y (1\u0026lt;\u003dx, y\u0026lt;\u003dN, x!\u003dy) is simply the bitwise AND of x and y. Now you are to find minimum spanning tree of this graph.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer T (1\u0026lt;\u003d T \u0026lt;\u003d10), the number of test cases. Then T test cases follow. Each test case consists of one line containing an integer N (2\u0026lt;\u003dN\u0026lt;\u003d200000)."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, you must output exactly 2 lines. You must print the weight of the minimum spanning tree in the 1st line. In the 2nd line, you must print N-1 space-separated integers f2, f3, … , fN, implying there is an edge between i and fi in your tree(2\u0026lt;\u003di\u0026lt;\u003dN). If there are multiple solutions you must output the lexicographically smallest one. A tree T1 is lexicographically smaller than tree T2, if and only if the sequence f obtained by T1 is lexicographically smaller than the sequence obtained by T2."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1 1\r\n0\r\n1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the 1st test case, w(1, 2) \u003d w(2, 1) \u003d 0, w(1, 3) \u003d w(3, 1) \u003d 1, w(2, 3) \u003d w(3, 2) \u003d 2. There is only one minimum spanning tree in this graph, i.e. {(1, 2), (1, 3)}.\u003cbr\u003eFor the 2nd test case, there is also unique minimum spanning tree.\u003cbr\u003e"}}]}