QUEST4  Dungeon of Death
To reach the treasure, Jones has to pass through the "Room of Death". The floor of this room is a square with side 120 units. It is laid with square tiles of dimensions {1 X 1} arranged into a grid. But, at some places in the grid tiles are missing. As soon as the door to this room is opened poisonous gas starts coming out of these missing grid locations. The only escape from this gas is to completely cover these locations with planks lying outside the room. Each plank has dimensions {120 X 1} and can only be placed parallel to either sides of the floor. Now Jones wants to minimize the damage to his health so that he has enough of it left for the treasure. He figures out that in order to achieve this he has to use the minimum number of planks possible. He also realises that even if the planks overlap, poisonous gas from the missing tiles can still be successfully blocked. Please help Jones in this task.
Input
 The first line of the input is a positive integer t <= 20, denoting the number of rooms.
 The descriptions for the t rooms follow one after the other.
 Room Description:
 The first line of the room description is a positive integer n (n <= 10010), denoting the number of missing tile locations.
 This is followed by the n lines, one for each missing tile location.
 Each line contains two integers x y (0 <= x, y < 120), separated by a single space, representing the coordinates of the missing tile location.
Output
The output should consist of t lines, one for each room. The k^{th} line in the output should be an integer m_{k}, the minimum number of planks needed for the k^{th} room.
Example
Input:
2
3
1 0
2 0
3 0
4
1 1
2 2
3 3
4 4
Output:
1
4
hide comments
joqsan_77:
20180824 14:46:27
Nice problem.


foodman47:
20170731 09:38:57
Last edit: 20170731 09:51:35 

npsabari:
20121008 17:47:20
Why 8s?? 
Added by:  Kashyap KBR 
Date:  20051208 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 