PERFECTR - Perfect Road

Byteland is a fictitious city commonly mentioned here on SPOJ.

An ancient legend tells that Bytelandians lived in a simple town, just like the Old Western California, where there was just a single straight road of about 500 Meters and all houses, bars and hotel had the road in front of them. In Byteland, although there is a small difference, here, including the Main Road, each house has its own road that connects to the main road, but according to the law, each particular road need to be perpendicular to the main road.

So their world can be abstracted as a two-dimensional grid with integer coordinates. The main road is the x-axis and houses are points connected perpendicularly to the x-axis (in both the positive and negative y directions).

In this particular city, if a person A needs to visit any other person B, he needs to walk along the street that connects his home to the main road until it reaches the main road, then walk through the main road up to the street that comes from the other home, and then walk this street to B's home. But in the case their homes are in the same street, they only need to walk the segment that connects their houses.

The distance between two persons home is defined as:

  1. If two homes have the same 'x' coordinate. The distance between them is the absolute difference between their 'y' coordinates. (This is the case where they live in the same street)
  2. Otherwise, the distance is the distance between Person A and the main road + the distance between Person B and the main road + the absolute difference between their 'x' coordinates.

Here are 3 persons, one at (1, 1), other at (1, 4), and the last one at (4, 1). This is the first example.

The government is about to make a bold decision that will make the lives of the bytelandians easier. They will minimize the maximum distance between any pair of persons by moving the main road to a horizontal line y = N, where N is an integer. If the main road is already at the optimal position, it will not be moved.

You will be given the 'x' and 'y' coordinates of the houses, print the maximum distance between any pair of persons after the main road is moved to the optimal position.

Input

The first line is T (3 ≤ T ≤ 1,000), the number of test cases, then T test cases follows.

Each test case starts with N (2 ≤ N ≤ 50), the number of persons in Byteland.

Then N lines, each one with two integers separated by a space.

Each one of these integers is the x and y coordinates, respectively, of a Bytelandian home.

Constraints:

The absolute value of each x and y coordinate will be between 0 and 109, inclusive.

Output

For each test case print out the required distance in a single line.

Example

Input:
3
3
1 4
4 1
1 1
5
-1 -1
-2 3
-1 -3
0 0
2 3
4
1 1
1 10
1 100
1 1000

Output:
6
9
999

Added by:Olson Ortiz
Date:2011-07-30
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32 ASM64 BASH BF C99 CLPS CLOJURE LISP sbcl LISP clisp D ERL FSHARP FORTRAN GO HASK ICON ICK JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PERL6 PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCALA SCM guile SCM qobi ST TCL WHITESPACE
Resource:Used in 2nd PUCMM-ACM-ISC Programming Olympiad phase1 (2011)

hide comments
2011-08-16 18:51:29 Olson Ortiz
@Linguo "The absolute value of each x and y coordinate will be between 0 and 10^9, inclusive."

It reads the absolute value, not the value with its sign.
2011-08-12 10:09:13 Luke Pebody
The sample data does not satisfy the constraints.

I assume the constraints should read that the coordinates are between -10^9 and 10^9 ?

This change of constraints changes the type of variable needed to store the answer, and led to me trying about 20 failed solutions...
2011-08-10 05:20:44 cjtoribio
True, i think it was not thought to be that low

O(N^2) was the one near the limit without hard optimisation

Last edit: 2011-08-10 05:23:21
2011-08-10 04:55:16 [Rampage] Blue.Mary
If the problem requires O(nlogn) solution, he should not set the limit of n to 50.
2011-08-10 04:31:51 cjtoribio
There is an O(NlogN) and a O(N^2) whithout hard optimisation

You probably found the O(N^2logMAX)

Last edit: 2011-08-10 05:23:35
2011-08-10 00:16:31 [Rampage] Blue.Mary
I don't like problem of this style. Heavy constant optimization is needed.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.