數線上有 $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