Sphere Online Judge

SPOJ Problem Set (classical)

709. The day of the competitors

Problem code: NICEDAY


The International Olympiad in Informatics is coming and the leaders of the Vietnamese Team have to choose the best contestants all over the country. Fortunately, the leaders could choose the members of the team among N very good contestants, numbered from 1 to N (3 ≤ N ≤ 100000). In order to select the best contestants the leaders organized three competitions. Each of the N contestants took part in all three competitions and there were no two contestants with equal results on any of the competitions. We say that contestant А is better than another contestant В when А is ranked before В in all of the competitions. A contestant A is said to be excellent if no other contestant is better than A. The leaders of the Vietnamese Team would like to know the number of excellent contestants.

Input

First line of the input contains an integer t (1 ≤ t ≤ 10 ), equal to the number of testcases. Then descriptions of t testcases follow. First line of description contains the number of competitors N . Each of the next N lines describes one competitor and contains integer numbers ai, bi, ci (1 ≤ ai, bi , ci ≤ N ) separated by spaces, the order of i-th competitor's ranking in the first competition , the second competition and the third competition.

Output

For each test case in the input your program should output the number of excellent contestants in one line.

Note : Because the input is too large so we have 4 input files and the total time limit is 4s ( not 1s ).

Example

Input:
1
3
1 2 3
2 3 1
3 1 2

Output:
3

Added by:Nguyen Minh Hieu
Date:2006-01-20
Time limit:1s
Source limit:10000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All except: ERL JS NODEJS PERL 6
Resource:Base on a problem from BOI

hide comments
2014-05-16 21:25:54 Luis Manuel Díaz Barón
the problem statement is awful it should be corrected, I needed to read comments to realize what it really means.
2013-12-09 20:37:35 Aristofanis Rontogiannis
Getting 100 in NKTEAM and WA here, whats wrong?
2012-06-25 00:44:41 Muhammad Fahmi Amir


Last edit: 2012-11-19 04:09:25
2012-05-27 05:11:39 Anand
if you think of the last condition, solution is on its way.
2011-10-30 08:07:49 Yêu em mãi mãi
@Akashs
you're wrong.
A is not excellent constestant if there exists 1 another constestant B score higher than A in ALL 3 competitions.
A=excellent constestant if A!=not excellent constestant.
Read the example again you'll see that the answer is 3.
2011-10-02 14:28:45 Md. M. I. Akashs
We say that contestant А is better than another contestant В when А is ranked before В in all of the competitions. A contestant A is said to be excellent if no other contestant is better than A. The leaders of the Vietnamese Team would like to know the number of excellent contestants."

in terms of this statement in the problem the result of the test case given in the problem should be 0. because in the first competition first contestant is better than all other contestant. In second competition third contestant is better than all other contestant. In third competition second contestant is better than all other contestant so result should be 0.
Am i right ?
2011-07-10 21:45:01 Carlos Joa
@problem setter: I'd like to add a test case to this proble. How can I contact you?
2011-07-03 02:20:09 Vladimir Kirichenkoff
Read the definitions carefully: a contestant A is excellent if no other contestant is better than A. Look at first contestant. The second contestant isn't better than the first and the third contestant isn't better than the first so the first contestant is excellent. And for other contestant written above is corrent so the answer for the testcase is 3, not 0

Last edit: 2011-07-03 02:20:46
2011-06-12 18:08:10 Santiago Palacio
There was no better candidate, all of them are at the same rank. (1 is not better than 1)
2011-06-01 06:03:26 hello
exactly. problem statement not clear..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.