Little Cyan Fish on lukusuoralla. Aluksi hän on kohdassa $a_0$, ja hänen kotinsa on kohdassa $0$.

Hän haluaa vierailla kohdissa $a_1, a_2, \ldots, a_n$ tässä järjestyksessä. Hän voi kävellä kumpaan tahansa suuntaan lukusuoraa pitkin. Milloin tahansa hän voi teleportata kotiinsa tai siirtää kotinsa nykyiseen kohtaansa. Molemmat toiminnot ovat ilmaisia, ja niitä voidaan suorittaa kuinka monta kertaa tahansa, myös kävelyn aikana.

Etsi pienin kokonaismatka, joka hänen täytyy kävellä vieraillakseen kaikissa kohdissa annetussa järjestyksessä.

Syöte

Syötteessä on useita testitapauksia. Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T$), joka ilmoittaa testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 5 \times 10^5$), joka ilmoittaa vierailtavien kohtien lukumäärän. Toinen rivi sisältää $n + 1$ kokonaislukua $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), jotka ilmoittavat alkukohdan ja vierailtavat kohdat.

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää yhden kokonaisluvun: pienimmän kokonaismatkan, jonka Little Cyan Fish joutuu kävelemään.

Esimerkit

Syöte 1

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

Tuloste 1

0
10
6
8

Huomautus

Ensimmäisessä esimerkkitestitapauksessa Little Cyan Fish teleporttaa kotiinsa kohtaan $0$, joten hänen ei tarvitse kävellä.

Toisessa esimerkkitestitapauksessa hän kävelee kohdasta $0$ kohtaan $10$ ja siirtää matkan varrella kotinsa kohtaan $5$. Sen jälkeen hän teleporttaa kohtaan $5$. Kokonaismatka on $10$.

Kolmannessa esimerkkitestitapauksessa hän kävelee kohdasta $0$ kohtaan $4$ ja siirtää matkan varrella kotinsa kohtaan $2$. Sen jälkeen hän teleporttaa kohtaan $2$ ja kävelee kohtaan $0$. Kokonaismatka on $4 + 2 = 6$.

Neljännessä esimerkkitestitapauksessa hän teleporttaa kohtaan $0$, kävelee kohtaan $3$ ja siirtää kotinsa kohtaan $3$. Sen jälkeen hän kävelee kohtaan $-2$ ja teleporttaa kohtaan $3$. Kokonaismatka on $3 + 5 = 8$.