H. AGAIN! Permutation with MAX Score
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

定义一个长度为 $$$n$$$ 的排列 $$$p$$$ 的得分 $$$score_p$$$ 为 $$$\sum_{i=1}^n[(\sum_{j=1}^i p_j)=k\times p_i]$$$，即在 $$$p$$$ 的所有下标中，前缀和是当前位置的值的 $$$k$$$ 倍的下标数量。

给定整数 $$$n$$$，你需要确定一个正整数 $$$k$$$，求出所有的长度为 $$$n$$$ 的排列中，得分的最大值是多少。

一个长度为 $$$n$$$ 的排列 $$$p$$$ 是指从 $$$1$$$ 到 $$$n$$$ 的每个整数恰巧在 $$$p$$$ 中出现一次，例如 $$$[3,1,2]$$$、$$$[1]$$$ 都是排列，但是 $$$[1,1,3]$$$、$$$[3,2,4]$$$ 都不是排列。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据，仅输入一个正整数 $$$n(1\le n\le 10^6)$$$，代表排列的长度。

保证同一测试点内 $$$n$$$ 的总和不超过 $$$10^6$$$。

Output

对于每组数据，输出共有两行：

第一行，一个整数 $$$k(1\le k\le 10^{12})$$$，代表你选择的整数 $$$k$$$。

第二行，一个长度为 $$$n$$$ 的排列，代表得分最高的排列。

任意满足题目要求的答案都是正确的。

Example
Input
6
1
2
3
4
5
6
Output
1
1
1
2 1
3
3 1 2
3
4 2 3 1
3
4 2 3 1 5
3
2 1 5 4 6 3
Note

在第三组输出样例中，使用红色标出了所有得分下标的数字 $$$[3,1,{\color{red}2}]$$$。

在第六组输出样例中，使用红色标出了所有得分下标的数字 $$$[2,{\color{red}1},5,{\color{red}4},{\color{red}6},3]$$$。