菲尼克斯决定成为一名科学家!他目前正在研究细菌的生长。
最初,在 $$$1$$$ 天,有一种细菌,质量为 $$$1$$$。
每天都会有一定数量的细菌分裂(可能为零或全部)。当一个质量为 $$$m$$$ 的细菌分裂时,它会变成两个质量为 $$$\frac{m}{2}$$$ 的细菌。例如,质量为 $$$3$$$ 的细菌可以分裂为质量为 $$$1.5$$$ 的两个细菌。
而且,每到夜晚,每种细菌的质量都会增加一倍。
Phoenix 想知道所有细菌的总质量是否有可能恰好为 $$$n$$$。如果可能的话,他对如何使用尽可能少的夜晚数获得该质量感兴趣。帮助他成为最好的科学家!
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^9$$$) - Phoenix 感兴趣的细菌质量总和。
输出
对于每个测试用例,如果细菌无法精确达到总质量 $$$n$$$,则打印 -1。否则,打印两行。
第一行应包含一个整数 $$$d$$$ — 所需的最少住宿天数。
下一行应包含 $$$d$$$ 整数,其中第 $$$i$$$ 整数表示应在第 $$$i$$$ 天分裂的细菌数量。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
3 9 11 2
输出 #1
3 1 0 2 3 1 1 2 1 0
注意
在第一个测试用例中,以下过程会产生总质量为 $$$9$$$ 的细菌:
- 天 $$$1$$$:质量为 $$$1$$$ 的细菌分裂。现在有两种细菌,每种细菌的质量为 $$$0.5$$$。
- 夜晚$$$1$$$:所有细菌的质量增加一。现在有两种质量为 $$$1.5$$$ 的细菌。
- Day $$$2$$$:无分割。
- 夜晚 $$$2$$$:现在有两种质量为 $$$2.5$$$ 的细菌。
- Day $$$3$$$:两种细菌分裂。现在有四种细菌,质量为 $$$1.25$$$。
- 夜晚$$$3$$$:现在有四种细菌,质量为$$$2.25$$$。
$$$ $$$
在第二个测试用例中,以下过程会产生总质量为 $$$11$$$ 的细菌:
- 天 $$$1$$$:质量为 $$$1$$$ 的细菌分裂。现在有两种质量为 $$$0.5$$$ 的细菌。
- 夜晚 $$$1$$$:现在有两种质量为 $$$1.5$$$ 的细菌。
- Day $$$2$$$:一种细菌分裂。现在存在三种质量为 $$$0.75$$$、$$$0.75$$$ 和 $$$1.5$$$ 的细菌。
- 夜间 $$$2$$$:现在存在三种质量为 $$$1.75$$$、$$$1.75$$$ 和 $$$2.5$$$ 的细菌。
- 天 $$$3$$$:质量为 $$$1.75$$$ 的细菌和质量为 $$$2.5$$$ 的细菌分裂。现在有五种细菌,其质量为 $$$0.875$$$、$$$0.875$$$、$$$1.25$$$、$$$1.25$$$ 和 $$$1.75$$$。
- 夜间 $$$3$$$:现在有五种具有质量的细菌 $$$1.875$$$、$$$1.875$$$、$$$2.25$$$、$$$2.25$$$ 和 $$$2.75$$$。
$$$ $$$
在第三个测试案例中,细菌在 $$$1$$$ 当天不分裂,然后在夜间 $$$1$$$ 生长为质量 $$$2$$$。