Terdapat $n$ kanguru pada sebuah garis bilangan, di mana kanguru ke-$i$ awalnya berada pada koordinat positif $c_i$ (yaitu, $c_i > 0$), dan memiliki dua panjang langkah $a_i$ dan $b_i$.

Kanguru-kanguru tersebut dikendalikan dengan menekan tombol 1, 2, 3, dan 4 pada papan ketik. Semua kanguru akan bergerak secara bersamaan sesuai dengan tombol yang ditekan. Secara spesifik, misalkan $x_i$ adalah koordinat saat ini dari kanguru ke-$i$:

• Tombol 1: Ia akan bergerak ke $(x_i + a_i)$.
• Tombol 2: Ia akan bergerak ke $(x_i - a_i)$.
• Tombol 3: Ia akan bergerak ke $(x_i + b_i)$.
• Tombol 4: Ia akan bergerak ke $(x_i - b_i)$.

Diperbolehkan bagi dua atau lebih kanguru untuk berada pada koordinat yang sama. Jika dua kanguru bertemu selama pergerakan, mereka hanya akan saling melewati satu sama lain.

Anda dapat menekan tombol-tombol tersebut sebanyak yang Anda inginkan. Maksimumkan banyaknya kanguru dengan koordinat negatif (yaitu, maksimumkan banyaknya kanguru dengan $x_i < 0$) setelah operasi-operasi tersebut.

Masukan

Terdapat beberapa kasus uji. Baris pertama dari masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama berisi sebuah bilangan bulat $n$ ($1 \le n \le 2 \times 10^5$) yang menyatakan banyaknya kanguru.

Untuk $n$ baris berikutnya, baris ke-$i$ berisi tiga bilangan bulat $a_i$, $b_i$, dan $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) yang mendeskripsikan kanguru ke-$i$.

Dijamin bahwa jumlah dari $n$ pada semua kasus uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, cetak satu baris yang berisi satu bilangan bulat, yang menyatakan banyaknya kanguru maksimum dengan koordinat negatif setelah operasi-operasi tersebut.

Contoh

Masukan 1

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

Keluaran 1

3
0