AT_tupc2024_l Square Connection

正の整数 $ s,t $ が与えられます。あなたは以下の操作を $ 0 $ 回以上好きな回数行うことができます。 - $ 1 $ 以上 $ 4 \times 10^{18} $ 以下の整数 $ u $ であって $ s+u $ が平方数であるものを選び、 $ s $ を $ u $ で置き換える $ s $ を $ t $ に一致させるために必要な操作の回数の最小値、およびその方法を一つ求めてください。 形式的には、以下を全て満たす長さ $ K $ の整数列 $ (u_1,u_2,\dots,u_K) $ を一つ求めてください。 - $ K $ は $ s $ を $ t $ に一致させるために必要な操作回数の最小値 - $ i=1,2,\dots,K $ に対して $ 1 \leq u_i \leq 4 \times 10^{18} $ - $ u_0=s $ とすると $ i=1,2,\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 $ 答えが複数ある場合はどれを出力しても正解とみなされる。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、 $ 8+1=9,1+3=4 $ はともに平方数です。また、 $ 1 $ 回の操作で $ 8 $ を $ 3 $ にすることは出来ません。 ### Constraints - $ 1 \leq T \leq 3 \times 10^5 $ - $ 1 \leq s, t \leq 10^9 $ - $ s \ne t $ - $ 1 $ つの入力ファイルに対する必要な操作回数 $ (=K) $ の総和は $ 10^6 $ 以下 - 入力は全て整数