说明

所谓“钟点秘书”，是指年轻白领女性利用工余时间为客户提供秘书服务，并按钟点收取酬金。“钟点秘书”为客户提供有偿服务的方式一般是：采用电话、电传、上网等“遥控”式服务，或亲自到客户公司处理部分业务。某跨国公司总裁正分身无术，为一大堆会议时间表焦头烂额，希望高级钟点秘书能做出合理的安排，能在有限的时间内召开更多的会议。每个会议i都有起始时间$b_i$和结束时间$e_i$，且$b_i<e_i$，即一个会议进行的时间为半开区间$[b_i，e_i$）。如果$[b_i，e_i$）与$[b_j，e_j$）均在“有限的时间内”，且不相交，则称会议i与会议j相容的。也就是说，当$b_i≥e_j$或$b_j≥e_i$时，会议i与会议j相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。

输入格式

第一行是一个整型数m(m<100)表示共有m组测试数据。

每组测试数据的第一行是一个整数n(1<n<10000)表示该测试数据共有n个活动。

随后的n行，每行有两个正整数$b_i,e_i(0<=b_i,e_i<24)$,分别表示第i个活动的开始与结束时间$（b_i<e_i)$

输出格式

对于每一组输入，输出最多能够安排的会议数量。

每组的输出占一行。

样例

2
10
3 6
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14
5
8 12
9 10
13 16
16 18
9 12

4
3

来源

《趣学算法》2.4节