题目描述

现在有 $2^n$ 枚戒指，第 $i$ 枚戒指的重量为 $m_i$，并满足 $m_1>m_2>\cdots>m_{2^n}>0$。也就是说，编号越小的戒指越重。

小魔女 A 会不断筛选戒指。假设当前还剩下 $k$ 枚候选戒指，她会将这 $k$ 枚戒指分成数量相同的两组，比较两组戒指的总重量，并保留总重量严格更大的一组。不断重复这一过程，直到只剩下一枚戒指，A 就会买下它。

小魔女 S 可以事先决定所有戒指的重量，也可以决定每一轮如何分组。她不会让任意一轮出现两组总重量相等的情况。

请你构造一种方案，使最终留下的戒指编号尽可能大。

本题为构造题。与原比赛的评分版本不同，本题不再根据最大重量评分：只要最终留下的戒指编号达到理论最优值，且整个构造合法，即可通过该测试点。

输入格式

第一行一个正整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行一个正整数 $n$，表示这一组有 $2^n$ 枚戒指。

保证 $1\le n\le20$，且单个测试文件中所有测试数据满足 $\sum 2^n\le2^{20}$。

输出格式

对于每组测试数据输出三行。

第一行输出一个正整数 $x$，表示你声称能够达到的最终戒指编号。你必须使 $x$ 为最大可能值。

第二行输出 $2^n$ 个正整数 $m_1,m_2,\ldots,m_{2^n}$，表示所有戒指的重量。必须满足 $1\le m_i\le10^{18}$ 且 $m_1>m_2>\cdots>m_{2^n}$。

第三行输出 $2^n$ 个整数 $t_1,t_2,\ldots,t_{2^n}$。其中：

• $t_i=0$ 表示第 $i$ 枚戒指最终留下；
• $t_i=r\ (1\le r\le n)$ 表示第 $i$ 枚戒指在第 $r$ 轮被淘汰。

t 数组需要完整描述一种合法的筛选过程。具体地，在第 $r$ 轮开始时，尚未被淘汰的戒指恰好是满足 $t_i=0$ 或 $t_i\ge r$ 的戒指。你必须保证：

• 满足 $t_i=r$ 的戒指恰有 $2^{n-r}$ 枚，它们构成本轮被淘汰的一组；
• 满足 $t_i=0$ 或 $t_i>r$ 的戒指也恰有 $2^{n-r}$ 枚，它们构成本轮保留的一组；
• 保留组的总重量严格大于淘汰组的总重量。

恰有一枚戒指满足 $t_i=0$，并且它的编号必须等于第一行输出的 $x$。

如果存在多种合法最优构造，输出任意一种即可。

输入输出样例

输入

1
2

输出

2
5 4 3 1
1 0 2 1

样例解释

样例中第一轮淘汰编号 $1,4$，保留编号 $2,3$。淘汰组重量为 $5+1=6$，保留组重量为 $4+3=7$。

第二轮淘汰编号 $3$，保留编号 $2$，且 $4>3$。因此最终留下第 $2$ 枚戒指。

数据范围与约定

对于所有测试数据：$1\le T\le20$，$1\le n\le20$，且每个测试文件满足 $\sum 2^n\le2^{20}$。

本题使用 Special Judge。评测器会验证你输出的最大编号是否最优、重量是否合法，以及每一轮分组是否满足题意。