數軸上面有 $n$ 隻袋鼠，當中第 $i$ 隻袋鼠一開始喺正座標 $c_i$（即係 $c_i > 0$），而且有兩個步長 $a_i$ 同 $b_i$。

呢啲袋鼠透過撳鍵盤上面嘅掣 1、2、3 同 4 嚟控制。所有袋鼠會根據撳落去嘅掣同時移動。具體嚟講，設 $x_i$ 為第 $i$ 隻袋鼠目前嘅座標：

• 掣 1：佢會移動到 $(x_i + a_i)$。
• 掣 2：佢會移動到 $(x_i - a_i)$。
• 掣 3：佢會移動到 $(x_i + b_i)$。
• 掣 4：佢會移動到 $(x_i - b_i)$。

允許兩隻或者更多袋鼠處於同一個座標。如果兩隻袋鼠喺移動過程入面相遇，佢哋只會直接穿過對方。

你可以隨意撳幾多次掣都得。請最大化操作之後處於負座標嘅袋鼠數量（即係最大化滿足 $x_i < 0$ 嘅袋鼠數量）。

輸入格式

有多組測試資料。輸入嘅第一行包含一個整數 $T$（$1 \le T \le 10^5$），代表測試資料嘅組數。對於每組測試資料：

第一行包含一個整數 $n$（$1 \le n \le 2 \times 10^5$），代表袋鼠嘅數量。

接落嚟嘅 $n$ 行，第 $i$ 行包含三個整數 $a_i$、$b_i$ 同 $c_i$（$-10^9 \le a_i, b_i \le 10^9$，$1 \le c_i \le 10^9$），用嚟描述第 $i$ 隻袋鼠。

保證所有測試資料入面 $n$ 嘅總和唔超過 $2 \times 10^5$。

輸出格式

對於每組測試資料，輸出一行包含一個整數，代表操作之後處於負座標嘅袋鼠嘅最大數量。

範例

輸入格式 1

2
4
1 1 1
-1 3 4
0 -2 7
-5 0 10
1
0 0 1

輸出格式 1

3
0