1463 - 第二届“华为杯”初赛题目H

Time Limit: 2s Memory Limit: 128MB

Submissions: 114 Solved: 30
Description

m个盒子,第i个盒子的长尾hi,宽为wi。如果两个盒子i,j满足hi<hjwi<wj,则盒子i能够放入盒子j。按照上述要求堆放盒子,则最少能剩下多少堆?

Input

第一行有一个正整数 t ,表示数据组数(不多于20)。每组数据第一行为m,表示盒子个数,1 ≤ m ≤ 20000。接下来一样有2m个正整数w1h1,w2h2, ... ,wmhm,分别表示盒子尺寸。其中对于任何i,1 ≤ wihi ≤ 10000. 

Output

每一组测试数据输出一样,为最少的堆数。

Sample Input
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
Sample Output
1
2
3
2
Hint
Source