新の交通方式

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

2115年的时候,地球人口已经突破**亿,这个时候高铁这种落后的交通工具因为座椅数目固定行车效率低下而被淘汰了,取而代之的是天才科学家晓楠发明的楠车。楠车具有各种各样的优点比如速度高达500m/s,没有加速时间,开车就能达到最大速度,甚至能够每一秒停一次车,另外最显著的一点就是在发车前可以自由的调整座位数目,这样就可以让楠车的运行效率大大提高!真是一个跨时代的发明。
楠车的速度极快,车上的每一个人都必须要有一个座位,如果站着的话会发生生命危险。
不过如果想要楠车的运行达到最有效率的状态,我们需要在发车前就计算出这一个车次最少需要多少个座位,天才科学家晓楠在这里突然不知道该怎么计算了,不过幸运的是,我们已经收集到了每个人的上车和下车的时间。聪明的你,能帮助晓楠解决这个问题吗?
当在一个时间点同时有人上车和下车的时候,我们遵循先下后上的规则,也就是说如果车上还有人要下车的时候,上车的人会一直等到想要下车的人全部下车为止。

Input

多组输入,第一行为一个T,代表一共有T组数据(T < = 10)
接下来每一组数据第一行都是一个整数n,代表一共有n个人来乘车(n < = 100000)
接下来有n行,每一行两个整数L,R(0 < = l < = r < = 1000000000)(以秒为单位)
分别代表这个人的上车和下车时间

Output

每组数组输出一行一个整数,代表这一发车至少需要的座位数

Sample Input

2
3
1 2
2 3
5 7
3
1 9
2 8
3 7

Sample Output

1
3

Hint

 

Source

QAsQ 2015级ACM集训队第二次选拔赛