思路

• 定义数的“平方因子核”函数：记 $\mathrm{sf}(x)$ 为 $x$ 的质因子中幂次为奇数的质因子相乘得到的数（即把所有平方因子剥去后得到的平方自由部分）。

• 关键性质：对任意正整数 $a,b$，有

  $a\cdot b \text{ 是完全平方数} \iff \mathrm{sf}(a)$ = $\mathrm{sf}(b).$

• 因此，将 $1\ldots n$ 按 $\mathrm{sf}(x)$ 相等分组。组内相邻两数乘积一定为平方数；不同组之间不可能为平方数。

• 若把每个组作为一个连续块并依次拼接，则代价为所有组内成功对数之和，即

题目内容

给定一个正整数 $n$ ，一个长度为 $n$ 的排列 $p$ 是由 {$1,2,...,n$} 这 $n$ 个整数按任意顺序组成的数组，其中每个整数恰好出现一次;

我们定义该排列的代价为满足 $p_i×p_{i+1}$ 是完全平方数的索引 $i$ 的个数 $(1 ≤i< n)$ ;

请你构造一个排列 $p$ ，使其代价最大。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 ≦T≦ 10^4)$ ，表示测试用例数;

此后 $T$ 行，每行输入一个整数 $n(2≦n≦2×10^5)$，表示排列的长度;

此外，保证所有测试用例的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每组测试数据，新起一行，输出一个长度为 $n$ 的排列 $p$ 为最大代价的排列。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

2
5
10

输出

2 3 1 4 5
10 7 6 1 4 9 2 8 3 5