Problem 海猫的奇妙分数

时间限制：1000ms

空间限制：256MB

题目描述

埃及法老海猫常年住在金字塔里，因此wife不好，很难与外界沟通。因此很多问题，只能靠身边的人解决。

最近海猫遇到了一个棘手的难题，因为他想要吃一些分子料理————萨米秘制速冻坍缩分子胶囊（以下简称分子胶囊）。但是由于工艺限制，一次只能制作n分之一份食材。而且制作时使用的机器还有些bug特性，每次生产分子胶囊时的n都不能一样。然而海猫想吃的分量确实一个不大于1的有理数。

于是海猫询问身边的rua牛应该如何解决。鉴于修理机器特性并改善工艺需要花费过长时间（论屎山代码是怎么来的），聪明rua牛提出，可以通过多个n分之一份分子胶囊凑出海猫想吃的分量(本程序依赖bug运行)。而为了尽快生产出分子胶囊，这些n的取值应该尽量小。

具体来说：对于海猫想吃的料理分量$\frac{a}{b}$，你需要帮助rua牛找到一系列不同的$n_i$，使得$\sum_{i=1}^{m} \frac{1}{n_i}=\frac{a}{b}$。对于符合条件的$\{n_i\}$，你只需要求出字典序最小的。

输入格式

第一行一个数字$q$，表示有有$q$次询问. 接下来$q$行，每行两个数$a$和$b$，表示海猫想吃的分量为$\frac{a}{b}$.

输出格式

输出$q$行数，每行为答案$\{n_i\}$.

样例输入1

5
4 4
3 4
2 4
1 4
7 19

样例输出1

1
2 4
2
4
3 29 1653

样例1解释

对于第二组数据，$\frac{3}{4}=\frac{1}{2}+\frac{1}{4}$. 对于第五组数据，$\frac{7}{19}=\frac{1}{3}+\frac{1}{29}+\frac{1}{1653}$. 可以证明$\{2,4\}$和$\{3,29,1653\}$是字典序最小的答案.

数据范围及约定

对于$60\%$的数据，$a \leq b , b \leq 10, q \leq 1$.

对于所有数据，$a \leq b , b \leq 1e5, q \leq 1e4$ $(n,m,a \in \mathbb{Z}^+)$.

保证所有答案再int类型范围内，为了防止数据溢出，尽量使用long long类型.