关键等价

对任意排列，记 $N_k$ 为“包含所有 $0,1,\dots,k-1$ 的子数组数量”。则

理由：某个子数组若 $mex = m$，它恰好对 $k=1,2,\dots,m$ 各贡献 $1$ 次（因为包含 $0,\dots,k-1$），对更大的 $k$ 不贡献，故总贡献为 $m$。

题目内容

给定一个正整数 $n$。在所有 $0,1,...,n-1$ 的排列 $a$ 中，定义任意子数组 $a_l,a_{l+1},...,a_r$ 的 $mex$ 为该子数组内未出现的最小非负整数。

请最大化所有子数组的 $mex$ 之和，即最大化 $\sum_{1≤l≤r≤n}mex(${$a_l,a_{l+1},...,a_r$}$)$

并输出该最大值及任意一个达到最大值的排列 $a$ 。

名词解释：

$mex$：对一个由非负整数构成的集合 $S，mex(S)$ 为不在 $S$ 中的最小非负整数。例如 $S=${$1,2$} 时 $mex(S)=0;S=${$0,1,3$} 时 $mex(S)=2$ 。

排列：本题中的排列指包含 $0,1,...,n-1$ 且每个恰好出现一次的长度为 $n$ 的序列。

子数组：形如 $a_l,a_{l+1},...,a_r(1 ≤l≤r≤ n)$ 的连续片段。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦ T ≦ 10^5)$ 表示数据组数。每组测试数据描述如下：

第一行输入一个整数 $n(1≦n≦10^5)$ 。

保证所有测试中 $n$ 的总和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，输出两行：

第一行输出一个整数，表示所有子数组的 $mex$ 之和的最大值；

第二行输出 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示任意一个达到最大值的排列。如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3
1
2
3

输出

1
0
3
0 1
7
1 0 2

说明

当 $n=1$ 时，唯一排列为 $[0]$ ，所有子数组仅有 $[0]$ ，其 $mex =1$ 总和为 $1$ 。

当 $n=2$ 时，取 $a=[0,1]$ 或 $[1,0]$ 均可使总和达到 $3$ 。