Round Hopscotch

問題文

座標平面上に，原点を中心とした半径 $1$ の円があり，円上に $N$ 個のマスがあります。
点 $(0,1)$ にあるマスをマス $0$ として円上に等間隔に時計回りにマス $0,1,2, \dots , N-1$ が並んでいます。
Alice と Bob ははじめ，それぞれマス $A,B \; (0 \leq A,B \leq N-1)$ にいて，$2$ 人はこれから以下の 移動 を同時に好きな回数行います。( $1$ 回も行わなくても構いません)

• Alice がマス $x \; (0 \leq x \leq N-1)$ にいるとき，Alice はマス $x+K \; (mod \; N)$ に移動する。
• Bob がマス $y \; (0 \leq y \leq N-1)$ にいるとき，Bob はマス $y+L \; (mod \; N)$ に移動する。

$2$ 人がともにマス $0$ にいるようにできるでしょうか。可能ならば必要な 移動 の回数の最小値を，不可能ならばそれを報告してください。

$1$ 回も移動せずとも二人ともマス $0$ にいる場合も，移動回数を $0$ 回として出力することに注意してください。

テストケースが $T$ ケース与えられるので，全てに答えてください。

想定解に誤りがありました。申し訳ございません。現在は修正されています。(2024/03/16 2:51)

制約

• $1 \leq T \leq 2*10^5$
• $1 \leq N \leq 10^6$
• $0 \leq A,B \leq N-1$
• $1 \leq K,L \leq N$
• 入力は全て整数である

入力

出力

$i \; (1 \leq i \leq T)$ 個目のテストケースについて，$2$ 人がともにマス $0$ にいるようにすることが可能ならば，必要な 移動 の回数の最小値を，不可能ならば -1 を，一行に出力してください。改行も忘れないようにしてください。

入力例 $1$

4
3 1 2 2 1
5 2 3 2 3
31 4 1 5 9
2 0 1 1 1

出力例 $1$

1
4
24
-1

$1$ つ目のテストケースについて，$1$ 回 移動 を行うことで，Alice は $1+2=3$ よりマス $0$ に，Bob は $2+1=3$ よりマス $0$ にいます。$0$ 回では両者がともにマス $0$ にいることはできないので，$1$ を出力します。
$2$ つ目のテストケースについて，$4$ 回 移動 を行うことで，Alice は $2+2*4=10$ よりマス $0$ に，Bob は $3+3*4=15$ よりマス $0$ にいます。$3$ 回以下では両者がともにマス $0$ にいることはできないので，$4$ を出力します。
$3$ つ目のテストケースについて，$24$ 回 移動 を行うことで，Alice は $4+5*24=124$ よりマス $0$ に，Bob は $1+9*24=217$ よりマス $0$ にいます。$23$ 回以下では両者がともにマス $0$ にいることはできないので，$24$ を出力します。
$4$ つ目のテストケースについて，何回移動しても $2$ 人がともにマス $0$ にいるようにはできないので，-1 を出力します。