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 co-ordinates 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