题目描述

连分数是以下形式的表达式：

$$a_0+\dfrac{1}{a_1+\dfrac{1}{a_2+\dfrac{1}{\ddots+\dfrac{1}{a_n}}}} $$

其中，$a_0, a_1, a_2,...,a_n$为非负整数。

给定一个分数 $\dfrac{x}{y}(x, y为正整数)$，请将其扩展为连分数。

输入

第一行包含一个整数 $T (1≤T≤10^3)$, 表示测试用例的数量。

每个测试用例的唯一一行包含两个整数 $x,y (1≤x,y≤10^9)$， 表示分数 $\dfrac x y$。可以保证 $gcd(x,y) =1$（x，y最大公约数为1）。

输出

对于每个测试用例，输出一行：首先是一个整数 $𝑛$ 表示连分数的高度，然后 $n + 1$ 个整数表示 $a_0, a_1, a_2,...,a_n$。您的解决方案应该保证，$0 \le n \le 100,0 \le a_i \le 10^9$。

样例输入#1

2
105 38
1 114

样例输出#1

4 2 1 3 4 2
1 0 114

提示

样例解释如下：

第一组：$\dfrac{105}{38}=2+\dfrac{1}{1+\dfrac{1}{3+\dfrac{1}{4+\dfrac 1 2}}}$

第二组：$\dfrac{1}{114}=0 + \dfrac{1}{114}$

来源

Problem - B - Codeforces