题解

这题题目要求 $2^{a_i}3^{b_i} \neq 2^{a_j}3^{b_j}$

那我们直接令所有的 $b = 0$，题目就变成了将一个 $n$ 转成 $2 ^ {a_i} + 2 ^ {a_{i + 1}} ...$，成了一个简单的二进制转换问题。

由于 $a_i$ 和 $b_i$ 的数量很有限，那么其 $a_ib_i$ 的组合数量也不多。

于是塔子哥猜测，出题人原本不是想考察这个。而是更像考察物品数量比较少，且背包容量比较大的，01背包恰好装满问题，这个可以用 最短路优化背包 的方法解决，但由于在笔试中这个难度有点超纲了，感兴趣的朋友可以自行了解。

问题描述

众所周知，任何一个数 $n$ 可以拆分为若干项，这些项是不同的，由 $2$ 的次幂和 $3$ 的次幂相乘之和组成，即：

且对于所有 $i$ 和 $j$ ，满足 $2^{a_i}3^{b_i} \neq 2^{a_j}3^{b_j}$

小红给你这个整数 $n$，希望你能找到这样两个长度为 $m$ 的序列 $A$ 和 $B$ 满足给出的方程($2^{a_1}3^{b_1},2^{a_2}3^{b_2},...,2^{a_m}3^{b_m}$)，并且按照由大到小的顺序依次输出。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1 < T < 100$），代表数据组数。每组测试数据描述如下：在一行上输入一个整数 $n$（$1 \leq n \leq 10^9$），代表给定的初始数字。

输出描述

对于每一组测试数据，第一行输出一个整数 $m$（$1 \leq m < 10^9$），代表序列的项数。第二行输出 $m$ 个不同的整数 $2^{a_1}3^{b_1},2^{a_2}3^{b_2},...,2^{a_m}3^{b_m}$，代表拆出的序列，并由大到小依次输出。

样例输入

5
10
15
123
3
321

样例输出

2
8 2
2
12 3
3
96 24 3
1
3
4
288 24 6 3

样例解释

1. 对于 $n = 10$，可以拆分为 $8 + 2$，其中 $8 = 2^3 \cdot 3^0$ 和 $2 = 2^1 \cdot 3^0$。
2. 对于 $n = 15$，可以拆分为 $12 + 3$，其中 $12 = 2^2 \cdot 3^1$ 和 $3 = 2^0 \cdot 3^1$。
3. 对于 $n = 123$，可以拆分为 $96 + 24 + 3$，其中 $96 = 2^5 \cdot 3^1$，$24 = 2^3 \cdot 3^1$ 和 $3 = 2^0 \cdot 3^1$。
4. 对于 $n = 3$，可以直接表示为 $3 = 2^0 \cdot 3^1$。
5. 对于 $n = 321$，可以拆分为 $288 + 24 + 6 + 3$，其中 $288 = 2^5 \cdot 3^2$，$24 = 2^3 \cdot 3^1$，$6 = 2^1 \cdot 3^1$ 和 $3 = 2^0 \cdot 3^1$。