この問題には添付ファイルがあります。粒子の動きをシミュレートして可視化するために使用できます。

VegiCat は $n$ 行 $n$ 列のグリッド上の粒子を観察しています。左下のマスの座標は $(1, 1)$ です。水平方向の座標は左から右に向かって増加し、垂直方向の座標は下から上に向かって増加します。各粒子は水平方向の向き（左または右）と垂直方向の向き（上または下）を持っています。各ステップの開始時に、各粒子は次のように向きを調整します：

• 水平方向の次のマスがグリッドの外にある場合、水平方向の向きを反転させる。
• 垂直方向の次のマスがグリッドの外にある場合、垂直方向の向きを反転させる。

これらの調整の後、$(x, y)$ にある粒子は 2 つの子粒子を生成します：

• 水平方向の向きが左ならば $(x - 1, y)$ に、右ならば $(x + 1, y)$ に 1 つ；
• 垂直方向の向きが下ならば $(x, y - 1)$ に、上ならば $(x, y + 1)$ に 1 つ。

どちらの子粒子も親の水平方向および垂直方向の向きを引き継ぎます。その後、親は消滅します。

向きに関わらず、複数の粒子が同時に同じマスを占めることがあります。それらは相互作用したり、互いの向きを変えたりしません。

時刻 $0$ において、$(x_0, y_0)$ には以下の向きの組を持つ 4 つの粒子が存在します：

• 右と上；
• 左と上；
• 右と下；
• 左と下。

各ステップにおいて、すべての粒子は同時に向きを調整し、その後上記のように分裂します。

$q$ 個のクエリが与えられます。各クエリでは整数 $A, B, C$ と時刻 $t$ が与えられます。各クエリについて、$Ax + By + C = 0$ を満たし、かつ時刻 $t$ に少なくとも 1 つの粒子を含むグリッドのマス $(x, y)$ の個数を求めてください。

入力

1 行目にはテストケースの個数を表す整数 $T$ ($1 \le T \le 10^5$) が与えられます。続いてテストケースの記述が与えられます。

各テストケースの 1 行目には 4 つの整数 $n, x_0, y_0, q$ ($2 \le n \le 10^9$, $1 \le x_0, y_0 \le n$, $1 \le q \le 10^5$) が与えられます。グリッドは $n$ 行 $n$ 列であり、初期マスは $(x_0, y_0)$、クエリは $q$ 個あります。

続く $q$ 行のそれぞれには 4 つの整数 $A, B, C$ と $t$ ($|A|, |B|, |C| \le 10^9$, $0 \le t \le 10^9$) が与えられます。これは時刻 $t$ における直線 $Ax + By + C = 0$ に対するクエリを表します。$A$ と $B$ が同時に $0$ になることはないことが保証されます。

すべてのテストケースにおける $q$ の総和は $10^5$ を超えないことが保証されます。

出力

各クエリについて、1 行に 1 つの整数を出力してください。すなわち、$Ax + By + C = 0$ を満たし、かつ時刻 $t$ に少なくとも 1 つの粒子を含むグリッドのマス $(x, y)$ の個数を出力してください。

入出力例

入力例 1

1
6 5 5 4
2 -1 -5 0
1 -1 0 1
11 45 14 2
1 0 -5 3

出力例 1

1
0
0
3

注記

下の図はサンプルにおける粒子の時間発展とクエリされた直線を示しています。灰色のマスは直線が通る格子点に対応するマスを表し、分裂方向はすべてグリッド内に収まるよう調整された後のものです。3 番目のクエリは考慮しているグリッドから遠すぎるため、3 番目のクエリの直線はここでは省略されています。

同じマスにあり同じ向きの組を持つ粒子は 1 つの記号として描かれており、重複度は省略されています。