本題附有附件。你可以用佢嚟模擬同埋視覺化粒子嘅移動。

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

說明

下面張圖展示咗範例入面粒子嘅演變過程，同埋查詢嘅直線，其中灰色格仔代表直線經過嘅整數點所在嘅格仔，而所有分裂方向都已經做咗合法性調整。由於第三個查詢離緊要考慮嘅網格太遠，呢度省略咗第三個查詢嘅直線。

同一個格仔入面具有相同方向組合嘅粒子會畫成單一個符號；重複嘅數量會被省略。