You are given an array A of N points in a 2−D plane, which denotes the location of houses of students. The students decided to meet at one of the houses to study together.
For travelling from a point in the plane [X1,Y1] to the point [X2,Y2], a student needs to travel a total distance of abs|X1−X2|+abs|Y1−Y2| i.e. the sum of the absolute difference between the differences in both the X and the Y coordinates.
Initially all the students are at their own house and they decide to meet in the house whose location is present in the array A such that the sum of total distances covered by other students to reach this house is minimum.
Input Format:
- The first line contains an integer T, which denotes the number of test cases.
- The first line of each test case contains an integer N, denoting the number of points in the plane.
- The next N lines of each test case contains 2 space-separated integers, X and Y, the coordinates of the houses on the plane.
Output Format:
For each test case, print the minimum distance travelled by all the students provided they choose the most optimal house.
Constraints:
1<=T<=10
1<=N<=105
1<=X,Y<=103
For first test case:
If the students meet at the house index 3 i.e. A[3]=[5,5], then the total distance covered will be,
For student indexed 1, abs(4-5) + abs(5-5) = 1.
For student indexed 2, abs(5-5) + abs(4-5) = 1.
For student indexed 3, abs(5-5) + abs(5-5) = 0.
Hence, the answer is 2.
For second test case:
If the students meet at the house index 2 i.e. A[2]=[7,8], then the total distance covered will be,
For student indexed 1, abs(9-7) + abs(9-8) = 3.
For student indexed 2, abs(7-7) + abs(8-8) = 0.
Hence, the answer is 3.
Another possible house is A[1]=[9,9], then the total distance covered will be,
For student indexed 1, abs(9-9) + abs(9-9) = 0.
For student indexed 2, abs(7-9) + abs(8-9) = 3.
Hence, the answer is 3.
