e-olymp
Yarışlar

January 22 - BMTK Programming School, High League - Segment Tree 2

День победителей

Приближается Международная олимпиада по информатике и во вьетнамскую команду следует набрать лучших участников со всей страны. К счастью, в команду смогли набрать n хороших участников, пронумерованных от 1 до n. Для выбора среди них наилучших решили организовать три соревнования. Каждый из n конкурсантов принял участие во всех трех соревнованиях, при этом никакие два участника не имеют одинаковых результатов ни в одном из соревнований. Будем говорить что участник А лучше участника В, если А стоит по рангу перед В во всех трех соревнованиях. Участник A является наилучшим, если ни один из других участников не лучше A. Лидеры вьетнамской команды хотят знать число наилучших участников.

Входные данные

Первая строка содержит количество тестов t (1t100 ). Далее следует описание t тестов. Первая строка содержит количество участников n (3n100000). Каждая из следующих n строк задает результаты одного участника и содержит числа ai, bi, ci (1ai, bi, cin) - ранги i-го участника в первом, втором и третьем соревнованиях.

Выходные данные

Для каждого теста вывести в отдельной строке количество наилучших участников.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
Giriş verilənləri #1
1
3
1 2 3
2 3 1
3 1 2
Çıxış verilənləri #1
3