NICEDAY - The day of the competitors

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 test cases. Then descriptions of t test cases 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:0.109s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Base on a problem from BOI

hide comments
2022-06-29 11:07:16
If using segment tree, then use FAST_IO else you may get TLE.
2021-01-22 22:57:08
I tried to sort all the contestants using
public int compareTo(Player o) {
if (this.a < o.a && this.b < o.b && this.c < o.c) return 1;
return 0;
}
but it's giving tle in java.
i have not done any thing only taken input and sorted then why its giving tle

2020-06-01 16:29:57
Good question

Last edit: 2020-06-01 16:50:01
2019-12-28 08:37:14
Solved using segment tree. Input format is different w.r.t NKTEAM question.
2019-11-02 18:18:34
solved with segment tree in 0.16s, hope will be much easier with BIT. See this blog if can't find out any idea... <gone>

Last edit: 2023-05-16 22:37:01
2019-10-20 15:52:33
simple implementation of BIT!!
2019-04-15 22:50:13
For those who didn't get the question-
A is a an excellent contestant if there exist no other contestant who secured a lower rank than A in all the three competitions;

Last edit: 2019-04-15 22:50:38
2018-11-09 11:17:33
Solved kind of same problem #NKTEAM. But here it gives WA. why?!!

update: Finally solved it using segment tree :)

Last edit: 2018-11-09 20:00:59
2017-09-22 06:36:36
Nice problem! If you can't understand, read carefully again.
If still can't understand, here it is - A player will not be excellent IF AND ONLY IF there exists another player, who is better than him in ALL 3 COMPETITIONS. So, in this example, player 1 is excellent because no player is better than him in all 3 competitions. Similarly, players 2 and 3 are also excellent.
2017-04-27 12:15:23 marzougi
Does any one not getting TLE with Java?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.