题目描述

有一堆木棍，总共有 $n$ 根。每根木棍的长度和重量都是预先已知的。这些木棍将被一台木工机器逐一加工。机器在准备加工一根木棍时需要一些时间，称为“准备时间”。这些准备时间与机器中的清洁操作以及更换工具和形状有关。木工机器的准备时间规定如下：

(a) 第一根木棍的准备时间为 1 分钟。

(b) 在加工完一根长度为 $l$、重量为 $w$ 的木棍后，如果下一根木棍的长度 $l'$ 和重量 $w'$ 满足 $l \leq l'$ 且 $w \leq w'$，则机器不需要额外的准备时间。否则，需要额外 1 分钟的准备时间。

你需要找到处理给定的 $n$ 根木棍所需的最小准备时间。例如，如果有 5 根木棍，它们的长度和重量分别为 (9, 4)、(2, 5)、(1, 2)、(5, 3) 和 (4, 1)，那么最小准备时间为 2 分钟，因为存在一个序列：(4, 1)、(5, 3)、(9, 4)、(1, 2)、(2, 5)。

输入

输入包含 $T$ 个测试用例。测试用例的数量 $T$ 在输入文件的第一行给出。每个测试用例包含两行：

• 第一行是一个整数 $n$，表示该测试用例中木棍的数量，满足 $1 \leq n \leq 5000$。
• 第二行包含 $2n$ 个正整数 $l_1, w_1, l_2, w_2, \dots, l_n, w_n$，每个整数的大小不超过 10000，其中 $l_i$ 和 $w_i$ 分别表示第 $i$ 根木棍的长度和重量。这 $2n$ 个整数之间用一个或多个空格分隔。

输出

输出应包含每个测试用例的最小准备时间（以分钟为单位），每行一个。

输入数据 1

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 

输出数据 1

2
1
3

来源

Taejon 2001