AT_tupc2024_l Square Connection

给定正整数 $s,t$。你可以进行如下操作任意（包括 $0$）次： - 选择一个满足 $1 \leq u \leq 4 \times 10^{18}$ 的整数 $u$，且 $s+u$ 是一个完全平方数，然后将 $s$ 替换为 $u$。 请你求使 $s$ 变为 $t$ 所需的最小操作次数，并给出其中一种操作方法。 形式化地说，请你找到一个满足以下条件的长度为 $K$ 的整数序列 $(u_1,u_2,\dots,u_K)$： - $K$ 是使 $s$ 变为 $t$ 所需的最小操作次数； - 对于所有 $i=1,\dots,K$，都满足 $1 \leq u_i \leq 4 \times 10^{18}$； - 设 $u_0=s$，则对所有 $i=1,\dots,K$，有 $u_{i-1}+u_i$ 是完全平方数； - $u_K=t$。 在本题的约束下，可以证明总能找到不超过 $10^6$ 次操作的方法使 $s$ 变为 $t$。 共有 $T$ 组测试用例，请分别回答每个询问。

输入以以下格式从标准输入读入。 > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 其中 $\text{case}_i$ 表示第 $i$ 个测试用例，每个测试用例格式如下： > $s$ $t$

输出共 $T$ 行。第 $i$ 行包含第 $i$ 个测试用例的答案，格式为： > $K$ $u_1$ $u_2$ $\dots$ $u_K$ 如果有多个方案，只需输出其中一种即可。

### 样例解释 1 对于第 $1$ 个测试用例，$8+1=9,\,1+3=4$ 都是完全平方数。另外，无法用一次操作将 $8$ 变为 $3$。 ### 约束条件 - $1 \leq T \leq 3 \times 10^5$ - $1 \leq s, t \leq 10^9$ - $s \ne t$ - 一个输入文件中所有操作次数 $K$ 的总和不超过 $10^6$ - 所有输入均为整数。 由 ChatGPT 5 翻译