配点 : $300$ 点

問題文

milktea 君は $x$ - $y$ 平面の原点に立っています。milktea 君が $(i,j)$ にいるとき、$1$ 回の移動で
$(i-1,j),(i+1,j),(i,j-1),(i,j+1)$ のいずれかに直線的に移動できます。
各移動の経路は格子点と格子点を結ぶ直線です。 これからちょうど $N$ 回の移動をして、再び原点に戻る移動を考えます。
ただし、原点のみ最初と最後の $2$ 回だけ訪れることができ、それ以外の格子点については $1$ 回までしか訪れてはいけません。
milktea 君が通った軌跡は自己交差の無い多角形となります。
(下図において、一番左の $1$ つは移動の条件を満たしますが、右の $3$ つは条件を満たしません。)

milktea 君は通った軌跡で構成される多角形の面積をちょうど $M$ にしたいと考えています。
また、できるだけ $x$ 座標の大きい点を通りたいと考えています。

milktea 君が通った軌跡が面積 $M$ の多角形となったとき、この過程で訪れた格子点の $x$ 座標の最大値が milktea 君の得点となります。
また、軌跡が面積 $M$ の多角形にならなかったとき、得点は $-1$ となります。

$T$ 個の各ケースに対して、milktea 君が得られる得点の最大値を答えてください。

制約

• $1 \leq T \leq 10^4$
• $4 \leq N \leq 10^9$
• $1 \leq M \leq 10^{18}$
• $N$ は偶数である
• 入力は全て整数である

入力

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

各ケースは以下の形式で与えられます。

出力

milktea 君が得られる得点の最大値を答えてください。
$i$ $(1 \leq i \leq T)$ 個目のケースに対する答えを $i$ 行目に出力してください。

サンプル

4
6 2
10 8
18 13
1000000000 5064265438408704

2
-1
7
489657536

$1$ つ目のケースについて、milktea 君は以下のように「→→↑←←↓」の順で $6$ 回の移動を行うことで、面積が $2$ の多角形を作ることができます。
このとき軌跡の中での $x$ 座標の最大値は $2$ であるため、得点は $2$ となります。

$2$ つ目のケースについて、$10$ 回の移動で面積が $8$ の多角形を作ることはできません。
そのため、millktea 君の得点は必ず $-1$ となります。