配点 :

問題文


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

図  

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

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

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

制約


  • は偶数である
  • 入力は全て整数である

入力


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





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

出力


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

サンプル


入力
4
6 2
10 8
18 13
1000000000 5064265438408704
出力
2
-1
7
489657536

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

図

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

提出


Go (1.14)