Snakes and their Discussions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
There are n snakes in Snakeland. Each snake can be denoted by either a horizontal or a vertical segment in the 2D grid.
The snakes want to hold a discussion over the benefits and limitations of capitalism. Two snakes can share their ideas with each other if they have at least one cell in common with each other. You want the snakes to have a proper discussion, i.e. each snake should be able to share their ideas with every other snake. In one second, you can move a snake horizontally or vertically by one unit. Also, you can move as many snakes simultaneously as you wish. Find the minimum number of seconds required to make this discussion possible.
Input
The first line of the input contains an integer T denoting number of test cases. The description of the T test cases follows.
The first line of each test case contains an integer n.
Each of the next n lines contains four space separated integers x_{1}, y_{1}, and x_{2}, y_{2}, denoting that the head of the snake is at (x_{1}, y_{1}) and the tail is at (x_{2}, y_{2}). It is guaranteed that snake will be denoted by either a horizontal or vertical segment.
Output
For each test case output a single integer corresponding to the answer of the problem.
Constraints
 1 ≤ T ≤ 50
 1 ≤ n ≤ 50
 1 ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ 50
Example
Input 3 2 1 1 1 3 1 1 3 1 2 1 1 1 3 2 1 3 1 3 1 1 1 3 2 1 3 1 2 2 2 2 Output 0 1 1
Explanation
Example 1. The snakes have a common cell at coordinates (1, 1). So, they will be able to talk to each other. There is no need to move them.
Example 2. Move the horizontal snake (i.e. 2, 1, 3, 1) to the left by 1 unit. It will now be (1, 1, 2, 1). Now, the first and second snakes will have at least one common cell and will be able to talk to each other. Hence, because you spent one second, the answer is 1.
Example 3. In the first second, move the first snake (i.e. 1, 1, 1, 3) to the right by 1 unit, it will be (2, 1, 2, 3). Also, simultaneously, move the second snake (2, 1, 3, 1) upwards by 1 unit. It will now be at (2, 2, 3, 2). So, after this one second, each pair of snakes have at least one common cell with each other and can talk and have a proper discussion.
Author:  admin2 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/SNDISCUS 
Tags  admin2, basicmath, greedy, proof, snckpb17 
Date Added:  31052017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, 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, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions