두 등산가

두 등산가가 어떤 산맥의 양쪽 끝에서, 정확히 같은 높이에 서 있다. 두 사람은 산맥을 따라 걸어서 서로가 출발한 지점에 도달하려 하는데, 이동하는 동안 두 사람의 높이는 항상 서로 같아야 한다. 높이를 같게 유지하기 위해 각 등산가는 산맥을 따라 앞으로도, 뒤로도 움직일 수 있다. 산맥이 출발 높이보다 낮아지는 곳이 없다면, 두 사람은 항상 이런 방식으로 서로의 출발 지점을 맞바꿀 수 있다. 산맥의 모양이 주어질 때, 두 등산가가 걷는 거리의 합의 최솟값을 구하여라.

산맥은 꼭짓점이 $p_i = (x_i, y_i)$인 꺾은선 $P = (p_1, p_2, \dots, p_n)$으로 나타낸다. 이 꺾은선은 $x$ 방향으로 단조롭다. 즉 $x_1 < x_2 < \dots < x_n$이며, 따라서 $x$에 대한 조각별 일차 함수의 그래프이다.

한 등산가의 이동은 $P$ 위의 점들의 수열 $W = (w_1, w_2, \dots, w_m)$으로, 이웃한 두 점 $(w_j, w_{j+1})$을 잇는 부분이 모두 $P$ 위에 있어야 한다. 한 걸음 $(w_j, w_{j+1})$의 길이는 높이 변화량 $|y(w_{j+1}) - y(w_j)|$만으로 측정하며(수평 이동은 길이에 포함되지 않는다), 이동 전체의 길이는 각 걸음 길이의 합이다. 등산가 A는 $p_1$에서, 등산가 B는 $p_n$에서 출발한다. 두 사람은 같은 높이에서 출발하므로 $y_1 = y_n$이다.

예를 들어 위 그림에서 왼쪽 등산가의 이동은 $(a, d, c, e, g, f, h, j, i, l, o, p, r, p, o, m, o, p, s)$이고, 이때 두 등산가가 걷는 거리의 합은 $120$으로 이것이 최솟값이다.

첫째 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 3$)가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 꺾은선 $P$의 꼭짓점 개수 $n$ ($3 \le n \le 1000$)이 주어진다. 이어지는 $n$개의 줄에는 점 $p_i$의 좌표가 $p_1, p_2, \dots, p_n$의 순서로, 각 줄마다 두 정수 $x_i$와 $y_i$ ($0 \le x_i, y_i \le 10000$)로 주어진다. $x$ 좌표는 순증가한다.

등산가 A는 $p_1$에서, 등산가 B는 $p_n$에서 출발하므로 $y_1 = y_n$이다. 모든 테스트 케이스에서 산맥은 출발 높이보다 낮아지지 않으며, 꼭짓점의 높이 $y_i$는 양 끝점이 출발 높이를 공유하는 것($y_1 = y_n$)을 제외하면 모두 서로 다르다.

각 테스트 케이스마다, 두 등산가가 걷는 거리의 합의 최솟값을 한 줄에 하나씩 출력한다.