Wooden Sticks

Interview

Time limit1sMemory limit128 MB

Summary

Given n sticks with length and weight, order them to minimize the number of setup steps, where a setup is needed unless both length and weight are nondecreasing from the previous stick.

Level: Medium5 of 10
Topics: Sorting, Greedy, Dynamic programming
Solved: No attempts yet

Problem

A woodworking shop has $n$ wooden sticks. Each stick has a fixed length and weight. The sticks are processed by a machine one at a time. Before processing a stick, the machine may need some time to be prepared for that stick — this is called the setup time. The setup time is determined by the following rules.

Processing the very first stick requires a setup time of 1 minute.
Suppose a stick of length $l$ and weight $w$ has just been processed, and the next stick to process has length $l'$ and weight $w'$ . If $l \le l'$ and $w \le w'$ , then no setup time is needed. Otherwise the machine must change its tool, so a setup time of 1 minute is required.

You may process the sticks in any order. Find the minimum total setup time needed to process all of the sticks.

For example, suppose there are five sticks $(4,9), (5,2), (2,1), (3,5), (1,4)$ . Processing them in the order $(1,4), (3,5), (4,9), (2,1), (5,2)$ needs a total setup time of 2 minutes, and this cannot be reduced any further, so the answer is 2.

Input

The first line contains the number of test cases $T$ .

Each test case consists of two lines. The first line contains the number of sticks $n$ ( $1 \le n \le 5000$ ). The second line contains $l_1\ w_1\ l_2\ w_2\ \dots\ l_n\ w_n$ separated by spaces, where $l_i$ and $w_i$ are the length and weight of the $i$ -th stick. All of these values are integers not greater than $10000$ .

Output

For each test case, print the minimum required setup time on its own line.

Examples1

Example 1

Input

3
5
4 9 5 2 2 1 3 5 1 4
3
2 2 1 1 2 2
3
1 3 2 2 3 1

Expected output

2
1
3