To attain inner peace Geek Sundaram has to pass through the "Hall of Valley of Death". The floor of this hall is a square with length 100 m. It is laid with square tiles of size 1 X 1 arranged over the entire hall. But, at some places in the hall tiles are broken. The moment a person enters the hall, the underworld awakens and dead souls emerge from these broken tiles. The only way to escape from these evil souls is to completely cover the broken locations with magic planks from the room of requirements. Each plank has size 100 X 1 and can only be placed parallel to either sides of the floor. Now Geek Sundaram has to save himself from these evil souls. He figures out that he has to use the minimum number of planks possible. Please help Geek Sundaram to attain inner peace.

Input

The first line of the input is a positive integer t <= 30, denoting the number of halls.
The descriptions for the t halls follow one after the other.
Hall Description:

The first line of the hall description is a positive integer n (n <= 10000), denoting the number of broken tile locations.
This is followed by the n lines, one for each broken tile location.
Each line contains two integers x y (0 <= x, y < 100), separated by a single space, representing the co-ordinates of the broken tile location.

Output
The output should consist of t lines, one for each hall. The k^th line in the output should be an integer mk, the minimum number of planks needed for the k^th hall.

Example
Input:
2
3
1 0
2 0
3 0
4
1 1
2 2
3 3
4 4

Output:
1
4

见题面

见题面