Hide

# Problem J

Nested Dolls

## 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 |