Маленькая Циановая Рыбка находится на числовой прямой. Изначально он находится в позиции $a_0$, а его дом — в позиции $0$.

Он хочет посетить позиции $a_1, a_2, \ldots, a_n$ именно в таком порядке. Он может идти вдоль числовой прямой в любом направлении. В любой момент времени он может телепортироваться к себе домой или переместить свой дом в свою текущую позицию. Оба этих действия бесплатны и могут выполняться любое количество раз, в том числе во время ходьбы.

Найдите минимальное суммарное расстояние, которое ему нужно пройти пешком, чтобы посетить все позиции в заданном порядке.

Входные данные

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит одно целое число $T$ ($1 \le T$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит одно целое число $n$ ($1 \le n \le 5 \times 10^5$) — количество позиций, которые нужно посетить. Вторая строка содержит $n + 1$ целых чисел $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — начальную позицию и позиции, которые нужно посетить.

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $5 \times 10^5$.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке одно целое число — минимальное суммарное расстояние, которое нужно пройти Маленькой Циановой Рыбке.

Примеры

Входные данные 1

4
1
7 0
2
0 10 5
3
0 4 2 0
3
-2 3 -2 3

Выходные данные 1

0
10
6
8

Примечание

В первом тестовом примере Маленькая Циановая Рыбка телепортируется к себе домой в позицию $0$, поэтому ему вообще не нужно идти пешком.

Во втором тестовом примере он идёт из $0$ в $10$ и по пути перемещает свой дом в позицию $5$. Затем он телепортируется в позицию $5$. Суммарное расстояние равно $10$.

В третьем тестовом примере он идёт из $0$ в $4$ и по пути перемещает свой дом в позицию $2$. Затем он телепортируется в $2$ и идёт в $0$. Суммарное расстояние равно $4 + 2 = 6$.

В четвёртом тестовом примере он телепортируется в $0$, идёт в $3$ и перемещает свой дом в $3$. Затем он идёт в $-2$ и телепортируется в $3$. Суммарное расстояние равно $3 + 5 = 8$.