Roof

You are going to build a new house. To estimate the minimum construction cost of the roof, you first need to know its height. You only have the outline of the house, so you must compute the roof height from that outline.

Here is the precise setup. The outline of the house is a rectilinear polygon: every edge is axis-parallel, either horizontal or vertical. Let $P$ be such a polygon with $n$ vertices.

The straight skeleton $SK(P)$ is the trace left by the vertices of $P$ as $P$ shrinks: every edge moves inward at the same speed while keeping its direction. Figure 1 (a) and (b) show this shrinking process for $P$ and the resulting $SK(P)$.

Figure 1

Now place $P$ on the $XY$ plane and shrink it at unit speed while simultaneously lifting it upward (the $+Z$ direction) at unit speed. As it moves, $P$ sweeps out a three-dimensional polyhedral surface called the terrain, and $SK(P)$ is exactly the projection of the terrain's edges onto the $XY$ plane. By construction every face of this terrain lies in a plane that makes a dihedral angle of $45^\circ$ with the $XY$ plane, and every face is bounded by at least one edge of $P$. We call this terrain the roof of $P$; Figure 1 (c) shows it.

The height of a point $q$ on the roof is its altitude, that is, the distance between $q$ and its projection onto the $XY$ plane. The height of the roof is the maximum height over all points on it. Your task is to compute the height of the roof of the given rectilinear polygon $P$.

The first line contains the number of test cases $T$.

Each test case begins with a line containing an integer $n$, the number of vertices of the polygon $P$, with $4 \le n \le 1000$. The next line lists the $(x, y)$ coordinates of the $n$ vertices of $P$ in counterclockwise order: first the $x$ and $y$ of the first vertex, then the $x$ and $y$ of the second vertex, and so on. All values are separated by single spaces, and every coordinate is an integer between $1$ and $100000$ inclusive.

For each test case print exactly one line: the height of the roof of $P$, written with exactly one digit after the decimal point.