本題附有附件。你可以使用它來模擬並視覺化粒子的移動。

VegiCat 在一個有 $n$ 列 $n$ 行的網格上觀察粒子。左下角格子的座標為 $(1, 1)$。水平座標由左至右遞增，垂直座標由下至上遞增。每個粒子都有一個水平方向（左或右）與一個垂直方向（上或下）。在每一步開始時，每個粒子會按以下方式調整其方向：

• 若其水平方向上的下一個格子在網格外部，則其水平方向反轉。
• 若其垂直方向上的下一個格子在網格外部，則其垂直方向反轉。

完成這些調整後，位於 $(x, y)$ 的一個粒子會產生兩個子粒子：

• 若其水平方向為左，則在 $(x - 1, y)$ 處產生一個；若為右，則在 $(x + 1, y)$ 處產生一個；
• 若其垂直方向為下，則在 $(x, y - 1)$ 處產生一個；若為上，則在 $(x, y + 1)$ 處產生一個。

兩個子粒子都會繼承父粒子的水平與垂直方向。接著父粒子消失。

多個粒子可以同時佔據同一個格子，無論它們的方向為何。它們之間不會產生交互作用，也不會改變彼此的方向。

在時間 $0$ 時，在 $(x_0, y_0)$ 處有四個粒子，具有以下方向配對：

• 右與上；
• 左與上；
• 右與下；
• 左與下。

在每一步中，所有粒子會同時調整各自的方向，然後如上所述進行分裂。

給定 $q$ 筆詢問。每筆詢問給出整數 $A, B, C$ 以及時間 $t$。對於每筆詢問，請找出在時間 $t$ 時滿足 $Ax + By + C = 0$ 且至少包含一個粒子的網格格子 $(x, y)$ 的數量。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 10^5$），代表測試資料的組數。接下來是各組測試資料的描述。

每組測試資料的第一行包含四個整數 $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$ 行中，每行包含四個整數 $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$。

輸出格式

對於每筆詢問，在一行中輸出一個整數：在時間 $t$ 時滿足 $Ax + By + C = 0$ 且至少包含一個粒子的網格格子 $(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

說明

下圖展示了範例中粒子的演化過程以及所詢問的直線，其中灰色格子代表包含直線所經過整數點的格子，且所有分裂方向皆已完成合法性調整。由於第三筆詢問距離所考慮的網格太遠，此處省略了第三筆詢問的直線。

同一個格子中具有相同方向配對的粒子會繪製為單一符號；重數在此省略。