Dilworth is the world’s most prominent collector of
Russian nested dolls: he literally has thousands of them! You
know, the wooden hollow dolls of different sizes of which the
smallest doll is contained in the second smallest, and this
doll is in turn contained in the next one and so forth. One day
he wonders if there is another way of nesting them so he will
end up with fewer nested dolls? After all, that would make his
collection even more magnificent! He unpacks each nested doll
and measures the width and height of each contained doll. A
doll with width
$w_1$ and
height
$h_1$ will fit in
another doll of width
$w_2$ and height
$h_2$ if and only if
$w_1<w_2$ and
$h_1<h_2$. Can you help him
calculate the smallest number of nested dolls possible to
assemble from his massive list of measurements?
Input
On the first line of input is a single positive integer
$1\leq t \leq 5$
specifying the number of test cases to follow. Each test case
begins with a positive integer $1
\leq m \leq 100\, 000$ on a line of itself telling the
number of dolls in the test case. Next follow $2m$ positive integers $w_1,h_1,w_2,h_2,\dots , w_ m, h_ m$,
where $w_ i$ is the width
and $h_ i$ is the height
of doll number $i$.
$1 \leq w_ i,h_ i \leq
10^9$ for all $i$.
Output
For each test case there should be one line of output
containing the minimum number of nested dolls possible.
Sample Input 1 |
Sample Output 1 |
4
3
20 30 40 50 30 40
4
20 30 10 10 30 20 40 50
3
10 30 20 20 30 10
4
10 10 20 30 40 50 39 51
|
1
2
3
2
|