POINTS - Point Nesting

no tags 

A point in 3D A (ax, ay, az) is said to nest another point B (bx, by, bz), iff bx <= ax AND by <= ay AND bz <= az. Given a set of 3D points, find a nesting sequence using maximal number of points. A sequence P0, P1, P2, ... is said to be a valid nesting sequence iff, P1 nests P0, P2 nests P1 and so on. Please note there could be duplicate points, and each input point must be used at most once while creating the sequence.

Input

First line contains the number of test cases T.
Each test case starts with n - the number of points. (0 < n <= 100,000)
The next n lines give the input points.

Output

For each test case print one integer saying the length of the longest nesting sequence.

Example

Input:
2
4
930887 692778 636916
747794 238336 885387
760493 516650 641422
202363 490028 368691
10
897764 513927 180541
383427 89173 455737
5212 595369 702568
956430 465783 21531
722863 665124 174068
703136 513930 979803
634023 723059 133070
898168 961394 18457
175012 478043 176230
377374 484422 544920

Output:
2
3

hide comments
Srivatsan B: 2009-05-05 15:15:26

I think this problem deserves to be in the main set, not the tutorial set.

Srivatsan B: 2009-05-05 04:26:51

I think the test data is a bit weak.
My first ACed submission should not pass when the largest nesting sequence contains two equal points (all coordinates equal), and that is allowed according to the task statement.


Added by:Prasanna
Date:2008-03-12
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:CMI Local Contest