Сан осінде $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$-ші жол $i$-ші кенгуруды сипаттайтын үш бүтін саннан $a_i$, $b_i$ және $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le 10^9$) тұрады.

Барлық тест жиынтықтарындағы $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