Permutation

题意翻译

给定 $n$，要求构造一个 $n$ 的排列 $a$，使满足 $a_{i-1} \cdot d=a_i$ 的 $i$ 个数尽可能多（$d$ 可以任选大于 $1$ 的正整数），输出这个排列以及你选择的 $d$

题目描述

Recall that a permutation of length $ n $ is an array where each element from $ 1 $ to $ n $ occurs exactly once. For a fixed positive integer $ d $ , let's define the cost of the permutation $ p $ of length $ n $ as the number of indices $ i $ $ (1 \le i < n) $ such that $ p_i \cdot d = p_{i + 1} $ . For example, if $ d = 3 $ and $ p = [5, 2, 6, 7, 1, 3, 4] $ , then the cost of such a permutation is $ 2 $ , because $ p_2 \cdot 3 = p_3 $ and $ p_5 \cdot 3 = p_6 $ . Your task is the following one: for a given value $ n $ , find the permutation of length $ n $ and the value $ d $ with maximum possible cost (over all ways to choose the permutation and $ d $ ). If there are multiple answers, then print any of them.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The single line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print the value $ d $ in the first line, and $ n $ integers in the second line — the permutation itself. If there are multiple answers, then print any of them.

输入输出样例

输入样例 #1

2
2
3

输出样例 #1

2
1 2
3
2 1 3