There are $n$ kangaroos on a number line, where the $i$-th kangaroo is initially at the positive coordinate $c_i$ (that is, $c_i > 0$), and has two step lengths $a_i$ and $b_i$.

The kangaroos are controlled by pressing the button 1, 2, 3 and 4 on the keyboard. All kangaroos will move simultaneously according to the button pressed. Specifically, let $x_i$ be the current coordinate of the $i$-th kangaroo:

• Button 1: It will move to $(x_i + a_i)$.
• Button 2: It will move to $(x_i - a_i)$.
• Button 3: It will move to $(x_i + b_i)$.
• Button 4: It will move to $(x_i - b_i)$.

It is allowed for two or more kangaroos to be at the same coordinate. If two kangaroos meet during the movement, they will simply pass through each other.

You can press the buttons as many times as you want. Maximize the number of kangaroos with a negative coordinate (that is, maximize the number of kangaroos with $x_i < 0$) after the operations.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^5$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$) indicating the number of kangaroos.

For the following $n$ lines, the $i$-th line contains three integers $a_i$, $b_i$ and $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) describing the $i$-th kangaroo.

It is guaranteed that the sum of $n$ of all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output one line containing one integer, indicating the maximum number of kangaroos with a negative coordinate after the operations.

Examples

Input 1

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

Output 1

3
0