На числовій прямій знаходяться $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