题目描述

现有n根木棒，已知它们的长度和重量。要用一部木工机一根一根地加工这些木棒。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。木工机需要的准备时间如下：

• （1）第一根木棒需要1min的准备时间；
• （2）在加工了一根长为$\red{l}$，重为$\red{w}$的木棒之后，接着加工一根长为$\red{ll}$（$\red{l<=ll}$），重为$\red{ww}$（$\red{w<=ww}$）的木棒是不需要任何准备时间的。否则需要一分钟的准备时间。 给定n根木棒，你要找到最少的准备时间。例如现在有长和重分别为（$\red{4}$,$\red{9}$），（$\red{5}$,$\red{2}$），（$\red{2}$,$\red{1}$），（$\red{3}$,$\red{5}$）和（$\red{1}$,$\red{4}$）的五根木棒，那么所需准备时间最少为2min，顺序为（$\red{1}$,$\red{4}$），（$\red{3}$,$\red{5}$），（$\red{4}$,$\red{9}$），（$\red{2}$,$\red{1}$），（$\red{5}$,$\red{2}$）。

输入格式

输入包含多组测试数据。输入的第一行是一个整数$\red{T}$，表示测试数据的个数。 每个测试例两行： 第一行是一个整数$\red{n}$（$\red{1<=n<=5000}$），表示有多少根木棒； 第二行包括$\red{n*2}$个整数，表示了$\red{l_1}$，$\red{w_1}$，$\red{l_2}$，$\red{w_2}$，$\red{l_3}$，$\red{w_3}$，...，$\red{l_n}$，$\red{w_n}$，这些数均不大于$\red{10000}$，其中$\red{l_i}$和$\red{w_i}$表示第$\red i$根木棒的长度和重量。

输出格式

输出以分钟为单位的最少准备时间。

样例

输入样例

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

输出样例

2
1
3