1 #include <cstdio>
2 #include <malloc.h>
3 #include <algorithm>
4 using namespace std;
5
6 struct nod
7 {
8 int l;
9 int w;
10 bool n;
11 };
12
13 int q_sort( nod *s3[5001],int q_head,int q_rear ) // 快排
14 {
15 int i = q_head-1;
16 int j = q_head;
17 for ( ; j < q_rear; ++j )
18 {
19 if ( s3[j]->l < s3[q_rear]->l )
20 {
21 ++i;
22 swap( s3[i]->l,s3[j]->l );
23 swap( s3[i]->w,s3[j]->w );
24 }
25 else if ( s3[j]->l == s3[q_rear]->l )
26 {
27 if ( s3[j]->w < s3[q_rear]->w )
28 swap( s3[j]->w,s3[q_rear]->w ); // 重点: 当两个长度相等时,要把重量按升序排列,因为这样才不会导致后来会少算!!!
29
30 }
31
32 }
33 swap( s3[i+1]->l,s3[q_rear]->l );
34 swap( s3[i+1]->w,s3[q_rear]->w );
35 return i+1;
36 }
37
38
39
40
41 void sort( nod *s2[5001],int head,int rear )
42 {
43 int i;
44 if ( head < rear )
45 {
46 i = q_sort( s2,head,rear );
47 sort( s2,head,i-1 );
48 sort( s2,i+1,rear );
49 }
50 }
51
52
53 int main()
54 {
55 //freopen( "in.txt","r",stdin );
56 int y;
57 scanf( "%d",&y );
58 while ( y != 0 )
59 {
60 int m;
61 scanf ( "%d",&m );
62 nod *s1[5001];
63 int l,w;
64 for ( int i = 0; i != m; ++i )
65 {
66 s1[i] = ( nod * )malloc( sizeof( nod ) );
67 scanf ( "%d%d",&l,&w );
68 s1[i]->l = l;
69 s1[i]->w = w;
70 s1[i]->n = false;
71 }
72 sort( s1,0,m-1 );
73 int time = 0;
74 for ( int i = 0; i != m; ++i ) // 贪心
75 {
76 if ( s1[i]->n == false )
77 {
78 int j = i;
79 int k = s1[i]->w;
80 while ( j != m )
81 {
82 if ( s1[j]->n == false && s1[j]->w >= k )
83 {
84 s1[j]->n = true;
85 k = s1[j]->w;
86 }
87 ++j;
88 }
89 ++time;
90 }
91 }
92 printf ( "%d\n",time );
93 --y;
94 }
95 return 0;
96 }
97