Friendly Knights
|
|
Gurram land is the city of Knights and is shaped exactly like a chess board. Some of the cells in this city contains Knights. Due to scarcity of grass ( Global Warming ! ), there has been fights between every pair of neighboring Knights. Knight A is a neighbor of Knight B, if A can reach B in exactly one step ( see notes for clarity ) . To spread peace in the Gurram land, the United Nations has organized a 'Friendship Mela' and wants to distribute friendship neck straps to the Knights. Each pair of neighboring Knights then exchange Neck Strap of same color and wear it around their neck, to promote friendship :). To make it more colorful, the UN also wants each Knight to have distinct colored neck straps around its neck. The UN is ready to produce any number of straps of a particular color, but can you help them to find out the minimum number of colors to be used. Notes: A Knight in cell (x,y) can move in one step to any of the cells (x+2,y+1) , (x+2,y-1) , (x+1,y+2) , (x+1,y-2) , (x-2,y+1) , (x-2,y-1) , (x-1,y+2) , (x-1,y-2) i.e., the normal rule in standard chess. |
Input
First line contains T ( around 10 ), the number of test cases. Each test case starts with an integer N ( 0 <= N <= 10000 ) the number of Knights in the city. Each of the next N lines contains two integers X Y the row and the column number of a Knight ( 1 <= X,Y <= 100 ). No two Knights are on a same cell.
Output
For each test case, print the minimum number of colors needed, in a separate line.
Example
Input:
2
3
1 1
2 3
3 2
4
1 1
2 3
2 1
1 3
Output:
2
1
Case 1 : (1,1) & (2,3) can exchange a Red strap , (1,1) & (3,2) can exchange a Green Strap
Case 2 : (1,1) & (2,3) can exchange a Red strap , (2,1) & (1,3) can exchange a Red Strap