文理学院程序设计在线练习


最少失约

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 269   Accepted Submission(s): 111
Problem Description

我们今天有许多重要的活动需要参加,可是由于活动太多,无法全部参加,请你帮我们安排,以便尽可能多地参加活动,减少失约的次数。(假设在某一活动结束的瞬间我们就可以立即参加另一个活动)

Input

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组测试数据。
每组测试数据首先是一个正整数n,代表当天需要参加的总的活动次数。以下的n行每行含有两个由空格隔开整数i和j,0<=i<j<24.分别代表活动的起止时间。

Output

对于每组测试数据。输出最少的失约总数。

Sample Input
3
2
1 3
3 5
5
1 4
3 5
3 8
5 9
12 14
12
1 2
3 5
0 4
6 8
7 13
4 6
9 10
9 12
11 14
15 19
14 16
18 20
Sample Output
0
2
5
Source

zscas第二届程序设计竞赛2008/03/30下午