数直線上に $n$ 匹のカンガルーがおり、$i$ 番目のカンガルーは最初、正の座標 $c_i$（すなわち $c_i > 0$）におり、2 つの歩幅 $a_i$ と $b_i$ を持っています。

カンガルーたちはキーボードのボタン 1, 2, 3, 4 を押すことで操作されます。押されたボタンに応じて、すべてのカンガルーが同時に移動します。具体的には、$i$ 番目のカンガルーの現在の座標を $x_i$ とすると：

• ボタン 1：$(x_i + a_i)$ に移動する。
• ボタン 2：$(x_i - a_i)$ に移動する。
• ボタン 3：$(x_i + b_i)$ に移動する。
• ボタン 4：$(x_i - b_i)$ に移動する。

2 匹以上のカンガルーが同じ座標にいることも許されます。移動中に 2 匹のカンガルーが出会った場合、単に互いにすり抜けます。

ボタンは好きなだけ何回でも押すことができます。操作後に負の座標にいるカンガルーの数（すなわち $x_i < 0$ となるカンガルーの数）を最大化してください。

入力

複数のテストケースがあります。入力の最初の行には、テストケースの個数を表す整数 $T$（$1 \le T \le 10^5$）が与えられます。各テストケースについて：

最初の行には、カンガルーの数を表す整数 $n$（$1 \le n \le 2 \times 10^5$）が与えられます。

続く $n$ 行のうち、$i$ 番目の行には $i$ 番目のカンガルーを表す 3 つの整数 $a_i$, $b_i$, $c_i$（$-10^9 \le a_i, b_i \le 10^9$、$1 \le c_i \le 10^9$）が与えられます。

すべてのテストケースにわたる $n$ の総和は $2 \times 10^5$ を超えないことが保証されます。

出力

各テストケースについて、操作後に負の座標にいるカンガルーの最大数を表す整数を 1 行に出力してください。

入出力例

入力 1

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

出力 1

3
0