Phoenix and Science

Description:

Input:

The input consists of multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the sum of bacteria masses that Phoenix is interested in.

Output:

For each test case, if there is no way for the bacteria to exactly achieve total mass $$$n$$$, print -1. Otherwise, print two lines.

The first line should contain an integer $$$d$$$  — the minimum number of nights needed.

The next line should contain $$$d$$$ integers, with the $$$i$$$-th integer representing the number of bacteria that should split on the $$$i$$$-th day.

If there are multiple solutions, print any.

Sample Input:

3
9
11
2

Sample Output:

3
1 0 2 
3
1 1 2
1
0 

Note:

In the first test case, the following process results in bacteria with total mass $$$9$$$:

• Day $$$1$$$: The bacterium with mass $$$1$$$ splits. There are now two bacteria with mass $$$0.5$$$ each.
• Night $$$1$$$: All bacteria's mass increases by one. There are now two bacteria with mass $$$1.5$$$.
• Day $$$2$$$: None split.
• Night $$$2$$$: There are now two bacteria with mass $$$2.5$$$.
• Day $$$3$$$: Both bacteria split. There are now four bacteria with mass $$$1.25$$$.
• Night $$$3$$$: There are now four bacteria with mass $$$2.25$$$.

The total mass is $$$2.25+2.25+2.25+2.25=9$$$. It can be proved that $$$3$$$ is the minimum number of nights needed. There are also other ways to obtain total mass 9 in 3 nights.

$$$ $$$

In the second test case, the following process results in bacteria with total mass $$$11$$$:

• Day $$$1$$$: The bacterium with mass $$$1$$$ splits. There are now two bacteria with mass $$$0.5$$$.
• Night $$$1$$$: There are now two bacteria with mass $$$1.5$$$.
• Day $$$2$$$: One bacterium splits. There are now three bacteria with masses $$$0.75$$$, $$$0.75$$$, and $$$1.5$$$.
• Night $$$2$$$: There are now three bacteria with masses $$$1.75$$$, $$$1.75$$$, and $$$2.5$$$.
• Day $$$3$$$: The bacteria with mass $$$1.75$$$ and the bacteria with mass $$$2.5$$$ split. There are now five bacteria with masses $$$0.875$$$, $$$0.875$$$, $$$1.25$$$, $$$1.25$$$, and $$$1.75$$$.
• Night $$$3$$$: There are now five bacteria with masses $$$1.875$$$, $$$1.875$$$, $$$2.25$$$, $$$2.25$$$, and $$$2.75$$$.

The total mass is $$$1.875+1.875+2.25+2.25+2.75=11$$$. It can be proved that $$$3$$$ is the minimum number of nights needed. There are also other ways to obtain total mass 11 in 3 nights.

$$$ $$$

In the third test case, the bacterium does not split on day $$$1$$$, and then grows to mass $$$2$$$ during night $$$1$$$.