Little Cyan Fish befindet sich auf einer Zahlengeraden. Zu Beginn ist er an Position $a_0$, und sein Zuhause befindet sich an Position $0$.

Er möchte die Positionen $a_1, a_2, \ldots, a_n$ in genau dieser Reihenfolge besuchen. Er kann entlang der Zahlengeraden in beide Richtungen laufen. Zu jedem Zeitpunkt kann er sich nach Hause teleportieren oder sein Zuhause an seine aktuelle Position verlegen. Beide Aktionen sind kostenlos und können beliebig oft ausgeführt werden, auch während er läuft.

Bestimme die minimale Gesamtdistanz, die er zu Fuß zurücklegen muss, um alle Positionen in der gegebenen Reihenfolge zu besuchen.

Eingabe

Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $T$ ($1 \le T$), die die Anzahl der Testfälle angibt.

Für jeden Testfall enthält die erste Zeile eine einzelne ganze Zahl $n$ ($1 \le n \le 5 \times 10^5$), die die Anzahl der zu besuchenden Positionen angibt. Die zweite Zeile enthält $n + 1$ ganze Zahlen $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), die die Startposition und die zu besuchenden Positionen angeben.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle $5 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer einzelnen ganzen Zahl aus, die die minimale Gesamtdistanz angibt, die Little Cyan Fish zu Fuß zurücklegen muss.

Beispiele

Eingabe 1

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

Ausgabe 1

0
10
6
8

Hinweis

Im ersten Beispieltestfall teleportiert sich Little Cyan Fish nach Hause an Position $0$, sodass er gar nicht laufen muss.

Im zweiten Beispieltestfall läuft er von $0$ nach $10$ und verlegt unterwegs sein Zuhause an Position $5$. Anschließend teleportiert er sich an Position $5$. Die Gesamtdistanz beträgt $10$.

Im dritten Beispieltestfall läuft er von $0$ nach $4$ und verlegt unterwegs sein Zuhause an Position $2$. Anschließend teleportiert er sich nach $2$ und läuft nach $0$. Die Gesamtdistanz beträgt $4 + 2 = 6$.

Im vierten Beispieltestfall teleportiert er sich nach $0$, läuft nach $3$ und verlegt sein Zuhause nach $3$. Anschließend läuft er nach $-2$ und teleportiert sich nach $3$. Die Gesamtdistanz beträgt $3 + 5 = 8$.