Divisor Chain
Contest: Harbour.Space Scholarship Contest 2023-2024 (Div. 1 + Div. 2)
Difficulty rating: 1300
Tags: bitmasks, constructive algorithms, math, number theory

You are given an integer $$$x$$$. Your task is to reduce $$$x$$$ to $$$1$$$.

To do that, you can do the following operation:

- select a divisor $$$d$$$ of $$$x$$$, then change $$$x$$$ to $$$x-d$$$, i.e. reduce $$$x$$$ by $$$d$$$. (We say that $$$d$$$ is a divisor of $$$x$$$ if $$$d$$$ is an positive integer and there exists an integer $$$q$$$ such that $$$x = d \cdot q$$$.)

There is an additional constraint: you cannot select the same value of $$$d$$$ more than twice.

For example, for $$$x=5$$$, the following scheme is invalid because $$$1$$$ is selected more than twice: $$$5\xrightarrow{-1}4\xrightarrow{-1}3\xrightarrow{-1}2\xrightarrow{-1}1$$$. The following scheme is however a valid one: $$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$.

Output any scheme which reduces $$$x$$$ to $$$1$$$ with at most $$$1000$$$ operations. It can be proved that such a scheme always exists.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The only line of each test case contains a single integer $$$x$$$ ($$$2\le x \le 10^{9}$$$).

Output format:
For each test case, output two lines.

The first line should contain an integer $$$k$$$ ($$$1 \le k \le 1001$$$).

The next line should contain $$$k$$$ integers $$$a_1,a_2,\ldots,a_k$$$, which satisfy the following:

- $$$a_1=x$$$;
- $$$a_k=1$$$;
- for each $$$2 \le i \le k$$$, the value $$$(a_{i-1}-a_i)$$$ is a divisor of $$$a_{i-1}$$$. Each number may occur as a divisor at most twice.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we use the following scheme: $$$3\xrightarrow{-1}2\xrightarrow{-1}1$$$.

In the second test case, we use the following scheme: $$$5\xrightarrow{-1}4\xrightarrow{-2}2\xrightarrow{-1}1$$$.

In the third test case, we use the following scheme: $$$14\xrightarrow{-2}12\xrightarrow{-6}6\xrightarrow{-3}3\xrightarrow{-1}2\xrightarrow{-1}1$$$.

Example input:
3
3
5
14

Example output:
3
3 2 1
4
5 4 2 1
6
14 12 6 3 2 1

Editorial:
Let us divide the task into two steps, on each step we will use each divisor at most once. For convenience, let us denote $$$L$$$ as the largest value, such that $$$2^L \le x$$$ holds. The two steps are as follows.
1. Reduce $$$x$$$ to $$$2^L$$$.Given any integer $$$x$$$, we can see that its lowest significant bit is a divisor of $$$x$$$. If $$$x$$$ has more than one bit, we can repeatedly subtract the value corresponding to the lowest significant bit of $$$x$$$. When $$$x$$$ finally has only one bit, finish the first step. In this step, we have only used each significant bit of $$$x$$$ at most once.
2. Reduce $$$2^L$$$ to $$$1$$$.We can find a way to reduce $$$2^L$$$ to $$$1$$$ by using each bit exactly once. Formally, if $$$k \ge 0$$$, then $$$2^{k+1}-2^k=2^k$$$, and $$$2^k$$$ is a divisor of $$$2^{k+1}$$$. Thus, by subtracting $$$2^{L-1},2^{L-2},\ldots,1$$$ in order, we reach $$$1$$$ from $$$2^L$$$ by using each bit from the $$$0$$$-th bit to the $$$(L-1)$$$-st bit exactly once.
As a result, we can reduce $$$x$$$ to $$$1$$$ by using each power of $$$2$$$ at most twice (once from the first step, once from the second step). Since we used each bit at most twice, the time complexity for solving one test case is $$$O(\log x)$$$.
Due to the lenient constraints, some solutions with $$$O(\sqrt x)$$$ time complexity should pass as well (as long as they fit into the $$$1000$$$ operations limit).