縦$H$マス横$W$マスの長方形のチェス盤があります。
チェス盤の上から $i$ 番目、左から $j$ 番目のマスを $(i, j)$ と表記します。
最初、$(r_k, c_k)$にナイトが、$(r_b, c_b)$にビショップが置いてあります。
以下の操作を繰り返し$2$つのコマを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより$2$つのコマを同じマスに集めることができない場合には$-1$を出力してください。

• どちらか$1$つのコマを選び、そのコマの動き方に従い$1$回動かす。
  ここで、それぞれのコマは以下のように動かすことができます:

  • ナイト: 置いてあるマスを$(a, b)$とすると、以下のいずれかの条件を満たすマス$(c, d)~(1 \leq c \leq H, 1 \leq d \leq W)$に動かすことができます。
    • $|a-c|=1$ かつ $|b-d|=2$
    • $|a-c|=2$ かつ $|b-d|=1$
  • ビショップ: 置いてあるマスを$(a, b)$とすると、以下の条件を満たすマス$(c, d)~(1 \leq c \leq H, 1 \leq d \leq W)$に動かすことができます。
    • $|a-c|=|b-d|$

$T$個のテストケースが与えられるので、それぞれについて答えを求めて下さい。

• $1 \leq T \leq 10^4$
• $2 \leq H \leq 3$
• $H \leq W \leq 10^9$
• $1 \leq r_k, r_b \leq H$
• $1 \leq c_k, c_b \leq W$
• $(r_k, c_k) \ne (r_b, c_b)$
• 入力は全て整数である
• $1$つの入力の中に $H=2$ を満たすテストケースと $H=3$ を満たすテストケースが混在することはない。

部分点

以下の条件を満たすデータセットに正解したとき、記載された点数が与えられる。

1. (20点) $H = 2$, ひとつの入力について、含まれる $W$の総和は$10^5$を超えない
2. (20点) $H = 3$, ひとつの入力について、含まれる $W$の総和は$10^5$を超えない
3. (30点) $H = 2$
4. (30点) $H = 3$

追加の制約がないデータセットは存在しない。つまり、部分点1~4に正答すると満点の100点が与えられる。

入力は以下の形式で標準入力から与えられる。

各テストケースは以下の形式で与えられる。

全体で $T$行出力せよ。
$i$行目には$i$個目のテストケースに対する答えを出力せよ。