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 翻译