Little Cyan Fish befinner sig på en tallinje. Ursprungligen är han på position $a_0$, och hans hem är på position $0$.

Han vill besöka positionerna $a_1, a_2, \ldots, a_n$ i denna ordning. Han kan gå i båda riktningarna längs tallinjen. När som helst kan han teleportera sig till sitt hem eller flytta sitt hem till sin nuvarande position. Båda handlingarna är gratis och kan utföras hur många gånger som helst, även medan han går.

Hitta den minsta totala sträckan han behöver gå för att besöka alla positioner i den angivna ordningen.

Indata

Det finns flera testfall. Den första raden i indatan innehåller ett enda heltal $T$ ($1 \le T$), som anger antalet testfall.

För varje testfall innehåller den första raden ett enda heltal $n$ ($1 \le n \le 5 \times 10^5$), som anger antalet positioner att besöka. Den andra raden innehåller $n + 1$ heltal $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), som anger startpositionen och positionerna som ska besökas.

Det garanteras att summan av $n$ över alla testfall inte överstiger $5 \times 10^5$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett enda heltal, vilket anger den minsta totala sträckan Little Cyan Fish behöver gå.

Exempel

Indata 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

Förklaring

I det första exempeltestfallet teleporterar sig Little Cyan Fish till sitt hem på position $0$, så han behöver inte gå.

I det andra exempeltestfallet går han från $0$ till $10$ och flyttar sitt hem till position $5$ på vägen. Därefter teleporterar han sig till position $5$. Den totala sträckan är $10$.

I det tredje exempeltestfallet går han från $0$ till $4$ och flyttar sitt hem till position $2$ på vägen. Därefter teleporterar han sig till $2$ och går till $0$. Den totala sträckan är $4 + 2 = 6$.

I det fjärde exempeltestfallet teleporterar han sig till $0$, går till $3$ och flyttar sitt hem till $3$. Därefter går han till $-2$ och teleporterar sig till $3$. Den totala sträckan är $3 + 5 = 8$.