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