\(s \gt t\) を仮定します．

任意の \(s,t\) に対して必要な操作回数は \(3\) 以下です．実際，十分大きい \(u \in \mathbb{N}\) であって \(u^2-s-t-1\) が偶数であるものを取り

\[s \to u^2-s \to \left(\dfrac{u^2-s-t-1}{2}\right)^2-t \to t\]

と操作すれば良いです．本問の制約下においては \(u\) として \(\sqrt{s+t}+2\) 程度の値を用いれば十分です．

以降 \(1\) 回，または \(2\) 回の操作で \(s\) を \(t\) に一致させることが可能かを判定します．

\(1\) 回の操作で可能な場合

\(s+t\) が平方数であることが必要十分条件です．

これは \(O(\log(s+t))\) や expected \(O(1)\) で判定することができます．前者は二分探索などで，後者は平方数をハッシュマップで管理することなどで実現できます．

\(2\) 回の操作で可能な場合

\(d=s-t\) とします．

\(d\) が奇数のとき

\(\left(\dfrac{d+1}{2}\right)^2 \gt s\) が必要十分条件です．

（十分性）

\[s \to \left(\dfrac{d+1}{2}\right)^2-s \to t\]

と操作すれば良いです．

（必要性） \(s+u = n^2, t+u = m^2\) なる \(u,n,m \in \mathbb{N}\) を任意にとると，

\[d = n^2 - m^2 \geq n^2 - (n - 1)^2 = 2n-1\]

なので \(n \leq \dfrac{d+1}{2}\) が必要です．

\(d\) が偶数のとき

\(d\) が \(4\) の倍数，かつ \(\left(\dfrac{d+4}{4}\right)^2 \gt s\) が必要十分条件です．

（十分性）

\[s \to \left(\dfrac{d+4}{4}\right)^2-s \to t\]

と操作すれば良いです．

（必要性） \(s+u = n^2, t+u = m^2\) なる \(u,n,m \in \mathbb{N}\) を任意にとると，\(n,m\) の偶奇が一致するので

\[d = n^2 - m^2 \geq n^2 - (n - 2)^2 = 4n-4\]

なので \(n \leq \dfrac{d+4}{4}\) が必要です．

これは \(O(1)\) で判定できます．

よって，適切な前計算の元で，テストケースあたり \(O(\log(s+t))\) や expected \(O(1)\) でこの問題を解くことができます．