Маленька Ціанова Рибка знаходиться на числовій прямій. Спочатку він перебуває в позиції $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$.

Вихідні дані

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

Приклади

Input 1

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

Output 1

0
10
6
8

Note

У першому прикладі Маленька Ціанова Рибка телепортується до свого дому в позиції $0$, тому йому не потрібно йти пішки.

У другому прикладі він іде з $0$ до $10$ і дорогою переміщує свій дім у позицію $5$. Потім він телепортується в позицію $5$. Сумарна відстань дорівнює $10$.

У третьому прикладі він іде з $0$ до $4$ і дорогою переміщує свій дім у позицію $2$. Потім він телепортується в $2$ і йде до $0$. Сумарна відстань дорівнює $4 + 2 = 6$.

У четвертому прикладі він телепортується в $0$, іде до $3$ і переміщує свій дім у $3$. Потім він іде до $-2$ і телепортується в $3$. Сумарна відстань дорівнює $3 + 5 = 8$.