All Submissions


There are two towers having M floors parallel to each other.To increase mobility between the towers N bridges are propsed to be build.A bridge will begin at 1st tower(any floor) and end at 2nd tower(any floor).Since bridges may intersect,authorities have come to you to tell them the maximum amount of bridges that can be build such that no two towers intersect.Bridges starting from same floor or ending on same floor is not considered as intersecting.

INPUT
The first line of input will contain the number of test cases T.Each test case will begin with one integer N indicating number of proposed bridges.Next line N lines will contain a pair of integers denoting the floor number of each tower for the propsed bridge.

OUTPUT
For each test case print the maximum number of non-intersecting bridges in separate line.

CONSTRAINT

0 < T <= 15
0 < N <=1000
0 < M <= 10^9


Sample Input

2
10
1 1
1 2
1 3
2 5
3 4
2 1
3 2
4 2
5 2
5 1
5
1 2
2 3
3 4
4 5
5 1

Sample Output

5
4


Problem Setter : Akshay Kumar
Problem Tester : Akshit Poddar


Languages: Brain,C,C++,Java,C#,JavaScript,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0