Có $n$ con chuột túi trên một trục số, trong đó con chuột túi thứ $i$ ban đầu ở tọa độ dương $c_i$ (tức là $c_i > 0$), và có hai độ dài bước nhảy $a_i$ và $b_i$.

Các con chuột túi được điều khiển bằng cách nhấn các nút 1, 2, 3 và 4 trên bàn phím. Tất cả các con chuột túi sẽ di chuyển đồng thời theo nút được nhấn. Cụ thể, gọi $x_i$ là tọa độ hiện tại của con chuột túi thứ $i$:

• Nút 1: Nó sẽ di chuyển đến $(x_i + a_i)$.
• Nút 2: Nó sẽ di chuyển đến $(x_i - a_i)$.
• Nút 3: Nó sẽ di chuyển đến $(x_i + b_i)$.
• Nút 4: Nó sẽ di chuyển đến $(x_i - b_i)$.

Cho phép hai hoặc nhiều con chuột túi ở cùng một tọa độ. Nếu hai con chuột túi gặp nhau trong quá trình di chuyển, chúng sẽ chỉ đơn giản là đi xuyên qua nhau.

Bạn có thể nhấn các nút bao nhiêu lần tùy ý. Hãy cực đại hóa số lượng chuột túi có tọa độ âm (tức là cực đại hóa số lượng chuột túi có $x_i < 0$) sau các thao tác.

Dữ liệu vào

Có nhiều bộ test. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^5$) cho biết số lượng bộ test. Đối với mỗi bộ test:

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2 \times 10^5$) cho biết số lượng chuột túi.

Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $a_i$, $b_i$ và $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) mô tả con chuột túi thứ $i$.

Đảm bảo rằng tổng của $n$ trong tất cả các bộ test không vượt quá $2 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ test, in ra một dòng chứa một số nguyên, cho biết số lượng chuột túi tối đa có tọa độ âm sau các thao tác.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

3
0