barbariks-special-arrows

Barbarik was the grandson of Bhima and the son of Ghatotkacha. Barbarik was supposed to be a brave warrior having learnt the art of warfare from his mother. Lord Shiva pleased with Barbarik's talent as a warrior granted him special arrows. Assuming the Battlefield as a 2D Grid, these arrows can kill all men standing in a row or in a column in 1 second . Before the war started, Lord Krishna asked everyone how long would it take for them to finish the war alone. Bhisma replied it would take 20 days. Dronacharya said it would take 25 days. Karna said it would take 24 days whereas Arjuna said it would take him 28 days.Krishna having heard of Barbarik and wanting to examine Barbarik's strength disguised himself as a Brahmin came in front of Barbarik. Krishna asked him the same question about how many days would it take to finish the war if he were to fight it alone. Barbarik seeks your help to answer this question. Assuming battlefield as a 2D grid of cells. Each cell may or may not contain a soldier. You are given the list of cells that contain warriors of opposite side. You have to tell the minimum number of seconds  that will be required by Barbarik to finish the war (killing all the soldiers).
 
Input 
The first line contains T the number of test cases. The first line of each test case contains N the number of cells where enemies are present. The following N lines contain two integers X and ** Y** each describing the index of the position of soldiers of opposite side. 
Output 
For each case print the minimum number of seconds that Barbarik need to finish the war alone. (kill all soldiers of opposite side ) 
Constraints 
1 ≤T ≤ 10 
1 ≤ N ≤ 1000 
0 ≤X, Y ≤ 1000000000 

SAMPLE INPUT
2
5
0 0
1 0
5 0
0 2
0 4
4
1 0
0 0
0 1
1 1

SAMPLE OUTPUT
2
2

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: