Two Mountaineers

Two mountaineers stand at opposite ends of a mountain range at exactly the same elevation. Each wants to walk along the range and reach the other climber's starting point, and throughout the journey the two must always stay at the same elevation. To keep their elevations equal, a climber may move either forward or backward along the range. As long as the range never drops below the starting elevation, the two climbers can always exchange starting points in this way. Given the shape of a mountain range, compute the minimum possible sum of the lengths of the two climbers' walks.

The mountain range is modeled as a polygonal chain $P = (p_1, p_2, \dots, p_n)$ with vertices $p_i = (x_i, y_i)$. It is monotone in the $x$-direction, i.e. $x_1 < x_2 < \dots < x_n$, so it is the graph of a piecewise-linear function of $x$.

A walk of a climber is a sequence of points $W = (w_1, w_2, \dots, w_m)$ on $P$ such that every consecutive part $(w_j, w_{j+1})$ lies on $P$. The length of a single step $(w_j, w_{j+1})$ is measured only by the change in elevation, $|y(w_{j+1}) - y(w_j)|$ (horizontal movement contributes nothing), and the length of the whole walk is the sum of the lengths of its steps. Climber A starts at $p_1$ and climber B starts at $p_n$; since they begin at the same elevation, $y_1 = y_n$.

For example, in the figure above, the left climber's walk is $(a, d, c, e, g, f, h, j, i, l, o, p, r, p, o, m, o, p, s)$, and the resulting sum of the two climbers' walk lengths is $120$, which is the minimum.

The first line contains the number of test cases $T$ ($1 \le T \le 3$).

Each test case is given as follows. The first line contains an integer $n$ ($3 \le n \le 1000$), the number of vertices of the polygonal chain $P$. Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($0 \le x_i, y_i \le 10000$), the coordinates of $p_i$, listed in the order $p_1, p_2, \dots, p_n$. The $x$-coordinates are strictly increasing.

Climber A starts at $p_1$ and climber B starts at $p_n$, so $y_1 = y_n$. In every test case the mountain range never drops below the starting elevation, and the vertex elevations $y_i$ are all distinct except that the two endpoints share the starting elevation ($y_1 = y_n$).

For each test case, print a single line containing the minimum possible sum of the two climbers' walk lengths.