本题没有可用的提交语言。

题目描述

两个登山者位于山脉的两端，处于相同的海拔高度。这两个登山者想要沿着山脉行走并到达对方的起始位置，同时始终保持在相同的海拔高度。登山者可以向前或向后移动，以确保他们处于相同的海拔高度。众所周知，如果山脉的高度永远不会低于起始海拔高度，那么这两个登山者总是能够到达对方的起始位置。给定一条山脉，计算两个登山者从各自的起始位置到达对方起始位置所行走的最小总路程。

山脉在平面上由一条折线 $P = (p_1, p_2, \ldots, p_n)$ 表示，点集为 $\{p_i = (x_i, y_i) : i = 1..n\}$，边集为 $\{(p_i, p_{i + 1}) : i = 1 \ldots n - 1\}$。对山脉建模的折线 $P$ 相对于 $x$ 坐标轴是单调的，即对于 $i = 1..n - 1$，有 $x_i < x_{i + 1}$（见下图）。

一个登山者沿着山脉 $P$ 的行走路线是一个点序列 $W = \{w_1, w_2, \ldots, w_m\}$，其中 $w$ 属于 $P$。行走路线中的每一条线段都必须在 $P$ 上。我们计算沿着线段 $(w_j, w_{j + 1})$ 的行走长度为 $w_j$ 和 $w_{j + 1}$ 的 $y$ 坐标之差，即 $|Y_j - Y_{j + 1}|$。行走路线 $W$ 的长度是 $W$ 中线段长度的总和。

例如，在上图中，左边登山者的行走路线是 $(a, d, c, e, g, f, h, j, i, l, o, p, r, p, o, m, o, p, s)$，两个登山者的行走长度总和是 $120$。我们可以看到这个长度是登山者行走的最短长度。

输入

输入由 $T$ 个测试用例组成。测试用例的数量 $T$ 在输入文件的第一行给出。每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 1000$），它是折线 $P$ 中的点数。在接下来的 $n$ 行中，每行有 $x_i, y_i$（$i = 1..n$）（$0 \leq x_i, y_i \leq 10000$）。一个登山者从 $p_1$ 出发，另一个从 $p_n$ 出发。因此，$y_1 = y_n$。你可以假设对于每个输入测试用例，山脉的高度永远不会低于起始海拔高度，并且 $y_i$ 是唯一的。

输出

对于每个测试用例，你的程序在每一行报告两个登山者行走的最小长度。以下示例输入和相应的正确输出表示三个测试用例。

输入样例

3
3
0 0
5 5
10 0
5
0 0
2 10
3 5
4 15
5 0
7
5 10
6 15
7 11
8 20
9 12
11 14
13 10

输出样例

20
100
120

题目来源

Taejon 2002