majorat

Task

You are given a positive integer $K$. Construct a sequence that has exactly $K$ subarrays, not necessarily disjoint, each admitting a majority element.

An element is considered a majority in a sequence of $N$ numbers if it appears at least $\lfloor \frac{N}{2} \rfloor + 1$ times.

The elements of the sequence must be positive integers between $0$ and the length of the sequence (inclusive).

Any sequence whose length belongs to the interval $[LOW, HIGH]$, where $LOW$ and $HIGH$ are specified in the problem constraints, is considered correct and will be scored accordingly.

You need to solve the problem for $T$ scenarios.

Input data

The first line of the input file contains the number $T$.
The next $T$ lines each contain a positive integer $K$, as described in the statement.

Output data

The output file will contain the solution for each of the $T$ scenarios. For each scenario, two lines will be displayed in the following format:

The first line will contain the length of the found sequence. The second line will contain the elements of the sequence, separated by a space.

Constraints and clarifications

• $1 \leq K \leq 1 \ 000 \ 000 \ 000$.
• For sequences with a length less than or equal to $LOW$, the maximum score will be awarded.
• For sequences with lengths in the interval $[LOW + 1, HIGH]$, between $20$ and $80$ percent of the score will be awarded according to the formula $\frac{80 \cdot (HIGH - N) + 20 \cdot (N - LOW)}{HIGH - LOW}$.
• For sequences longer than $HIGH$, zero points will be awarded.
• In a test case, the final score is the minimum obtained across all $T$ scenarios.
• It is guaranteed that a solution always exists that satisfies the problem constraints.
• $1 \leq \sum{HIGH} \leq 10^7$

Example 1

stdin

1
2

stdout

2
0 1

Explanation

For the first example, for the sequence {$0, 1$}, the subsequences are: {$0$} and {$1$}.

Example 2

stdin

2
5
2

stdout

3
1 0 0
2
1 2

Explanation

For the second example, for the sequence $\{1, 0, 0\}$, the subsequences are: $\{1\}$, $\{0\}$, $\{0\}$, $\{0, 0\}$, and $\{1, 0, 0\}$. For the sequence $\{1, 2\}$, the subsequences are: $\{1\}$ and $\{2\}$.