数式が与えられて、変形できそうであれば、なにはなくとも式変形。
とする。
(1)は最小公倍数、最大公約数を実装したことあればソースコードにこのように書いていると思う。
ここでfig.1のようなことを考えると、Aは、から共通因数を消した数だとわかる。
（素因数分解したときの共通部分が最大公約数）
よってAが平方数のときxとyは隣接。
つぎにAが平方数になる条件を考える。
x,yをそれぞれgcd(x,y)で割った数をとする。
（）
は共通因数を含まないので、それぞれ素因数分解をしたとき、含まれる素因数が2の倍数ずつなら平方数となる。
たとえば、なら、素因数a,b,cが2の倍数ずつ含まれるので、平方数（
）となる。
同様に、平方数平方数=平方数なので、
が平方数のとき、Aは平方数。
ここから発想の転換が必要。
というのもいままでのアイデアだと隣り合った値が隣接かどうかは判定できるが、任意の値が隣接か判定するにはO()かかってしまう。
まずよく考えると、gcdとなる共通部分を厳密に管理する必要は無いことに気づく。
というのも、判定したいのはBが平方数かどうか＝Bに含まれる素因数がそれぞれ偶数個かどうか、になる。
Bが平方数となる条件は、に含まれる素因数の個数がそれぞれ偶数個、とわかったので、Bが平方にならない条件は、
に含まれる素因数の個数が奇数となるものが存在する、となる。
（ただしは互いに素（共通する素因数を含まない））
ここで、x,yの素因数分解を考えて、それぞれ奇数個の素因子がわかったとする。
素因子の個数が偶数であればBは平方数になれるので状態としてもつ必要はない。
素因子の数が奇数かつ、x,yに同数ふくまれれば、gcdの約分で消える。
つまり、素因子の数が奇数かつ、x,yの共通因子として消えない分があるかどうかでBが平方数か判定できる。
まとめると、x,yの素因数のうち奇数個のものがすべてx,yの共通因数に含まれれば、平方数となる。
よって、「D=xの素因数のうち奇数個の素因数の積」と「F=yの素因数のうち奇数個の素因数の積」が等しい時平方数となる。
（偶数分の指数部分は消えるので、指数部分を考慮する必要ない（全て素因数として積を取る）
次にターン数が進んだ時を考えるが、ほとんどは共通部分の積として消えしまうので、各ターンで非共通部分としてなにが残るかを考える。
隣接するものの積をとるので、隣接する＝ D=Fなので、これらの積をとると、DとFが共通因数として現れることになる。
よって隣接する項数が偶数なら、素因数の個数は全て偶数となり消えて、奇数ならDが残ることになる。
さらに次のターンで何が起こる？
1ターン目で隣接する項数が偶数なら平方数となっていて、Dとして残ったものは全体に奇数個あるはずなので以降変化は起きない。
（D=Fとなる項数は奇数なので次ターンでもこれらはDのまま同じ数存在しつづける）
まとめ
全てのについて「
の素因数のうち奇数個のものの積」を管理する（これを
とする）。
（奇数個の素因数がない場合平方数なのでは1としておく。平方数
平方数は平方数）
0ターン目のうち等しいものの個数の最大値が答え。
1ターン目、隣接する個数の偶奇によってシミュレーションをして0ターン目と同様に求める。
2ターン目以降、1ターン目と答えは変わらない。
注意点
テストケースの数が大きい()ので、毎回素因数分解をしていては間に合わない。
予め の取りうる範囲、1から
の素因数の個数が奇数個の積を求めておき、再利用する。
それでも素因数分解では間に合わなかったので、の倍数を割れるだけ割っていって、同様のテーブルを用意した。
クエリ内のwを32bitで受け取らないように注意。
クエリを一括でstdoutしないとTLEだった、というかこの変更をしても2sギリギリ(1990ms)なので、もっと良い解法がある？
この方法でAC。
