Divide And Rule

All submissions for this problem are available.
East India company wants to eliminate all the pirates of the Carribbean. Lord Cutler Beckett has come up with a brilliant plan to crush all that's left of the pirates. Consider the whole sea of caribbean as a grid of infinite width and length, Beckett decides that he will use the oldest and the greatest strategy of all times  Divide and Rule. The sea contains N islands. Beckett has analysed the entire Carribean and marked the coordinates of each island present as (X_{i},Y_{i}) . The islands are assumed to be a point lying exactly on the grid point.
To destroy the pirates, at each pirate island he will construct two mutually perpendicular infinite length fences parallel to x and y axis crossing each other only at the island itself. This will create many partitions of the sea which will then be attacked separately to outpower the pirates. Fences constructed may overlap or cut each other but each fence extends to the infinity in both X and Y direction. Only partitions with nonzero area will be considered, thus all the overlapping fences need to be considered as one fence only.
The Beckett needs to train his huge army in a number of battalions to kill the pirates. One battalion can attack one and only one partition of the grid. The battalions are trained enough to beat any number of pirates, thus they always win in their partition. Your task is to calculate the number of battalions to be trained to make the pirate race extinct.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case gives the number of islands N. The next N lines will contain two integers, X_{i} and Y_{i} denoting the coordinates of the i^{th} island.
Output
For each test case, output a single integer representing the number of battalions which will have to be trained by Beckett.
Constraints
 1 <= T <= 10
 0 <= N <= 10000
 100000 <= X_{i} , Y_{i} <= 100000
Example
Input 2 2 2 2 3 3 2 2 2 3 2
Output 9 6
Explanation
In the first test case there will be 9 partitions as shown in the figure below
Author:  divanshu 
Tags  divanshu 
Date Added:  22102013 
Time Limit:  0.131579 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions