Interstellar Trade

As a rare reward for passing one of his inscrutable tests, Q has offered Commander Sisko the chance to relocate both ends of the Bajoran wormhole, and Deep Space Nine along with it. The Commander asked for relocation proposals, and several merchants want the ends moved into known space to cut the travel time between planets known for their commerce. Your job is to place the two ends of the wormhole so that the largest distance between any pair of these planets is as small as possible.

All planets of interest lie on one straight line, and without the wormhole the distance between two of them is simply the straight-line distance. Once the wormhole is in place, a traveler also has the option of flying from one planet straight to one end of the wormhole, then from the other end straight to the destination planet. The distance of that trip is the sum of the two flights, since crossing between the two ends takes no time. A traveler may always skip the wormhole, even when an end lies directly between the two planets. You may also place an end arbitrarily close to a planet, so the distance from that planet to the wormhole is effectively zero.

The first line contains one integer $T$ ($1 \le T \le 50$), the number of test cases.

Each test case begins with a line containing one integer $N$ ($2 \le N \le 4000$), the number of planets. The next $N$ lines each contain one integer $x_i$ ($-10^9 \le x_i \le 10^9$), the location of planet $i$. All planets are points on the x-axis, and no two planets sit at the same location.

For each test case, print on a single line the largest distance between any pair of planets once the wormhole has been placed so as to minimize that value. If the value is not an integer, round it up.

Planet locations are given as integers, but the ends of the wormhole may sit at non-integer coordinates.