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