Little Cyan Fish befinner seg på en tallinje. Opprinnelig er han på posisjon $a_0$, og hjemmet hans er på posisjon $0$.

Han ønsker å besøke posisjonene $a_1, a_2, \ldots, a_n$ i denne rekkefølgen. Han kan gå i begge retninger langs tallinjen. Når som helst kan han teleportere til hjemmet sitt eller flytte hjemmet sitt til sin nåværende posisjon. Begge handlingene er gratis og kan utføres så mange ganger han vil, inkludert mens han går.

Finn den minste totale avstanden han må gå for å besøke alle posisjonene i den gitte rekkefølgen.

Inndata

Det er flere testtilfeller. Den første linjen i inndataen inneholder ett enkelt heltall $T$ ($1 \le T$), som angir antall testtilfeller.

For hvert testtilfelle inneholder den første linjen ett enkelt heltall $n$ ($1 \le n \le 5 \times 10^5$), som angir antall posisjoner som skal besøkes. Den andre linjen inneholder $n + 1$ heltall $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), som angir startposisjonen og posisjonene som skal besøkes.

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $5 \times 10^5$.

Utdata

For hvert testtilfelle, skriv ut én enkelt linje som inneholder ett enkelt heltall, som angir den minste totale avstanden Little Cyan Fish må gå.

Eksempler

Inndata 1

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

Utdata 1

0
10
6
8

Merk

I det første eksempeltesttilfellet teleporterer Little Cyan Fish til hjemmet sitt på posisjon $0$, så han trenger ikke å gå.

I det andre eksempeltesttilfellet går han fra $0$ til $10$ og flytter hjemmet sitt til posisjon $5$ på veien. Deretter teleporterer han til posisjon $5$. Den totale avstanden er $10$.

I det tredje eksempeltesttilfellet går han fra $0$ til $4$ og flytter hjemmet sitt til posisjon $2$ på veien. Deretter teleporterer han til $2$ og går til $0$. Den totale avstanden er $4 + 2 = 6$.

I det fjerde eksempeltesttilfellet teleporterer han til $0$, går til $3$ og flytter hjemmet sitt til $3$. Deretter går han til $-2$ og teleporterer til $3$. Den totale avstanden er $3 + 5 = 8$.