Little Cyan Fish er á talnalínu. Upphaflega er hann í stöðu $a_0$ og heimili hans er í stöðu $0$.

Hann vill heimsækja stöðurnar $a_1, a_2, \ldots, a_n$ í þessari röð. Hann getur gengið í hvora áttina sem er eftir talnalínunni. Hvenær sem er getur hann fjarflutt sig heim til sín eða fært heimili sitt í núverandi stöðu sína. Báðar aðgerðirnar eru ókeypis og má framkvæma hversu oft sem er, þar á meðal á meðan hann gengur.

Finndu lágmarks heildarvegalengd sem hann þarf að ganga til að heimsækja allar stöðurnar í gefinni röð.

Inntak

Það eru mörg prófunartilvik. Fyrsta línan í inntakinu inniheldur eina heiltölu $T$ ($1 \le T$), sem gefur til kynna fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan eina heiltölu $n$ ($1 \le n \le 5 \times 10^5$), sem gefur til kynna fjölda staða sem á að heimsækja. Önnur línan inniheldur $n + 1$ heiltölur $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), sem gefa til kynna upphafsstöðuna og stöðurnar sem á að heimsækja.

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $5 \times 10^5$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu sem inniheldur eina heiltölu, sem gefur til kynna lágmarks heildarvegalengd sem Little Cyan Fish þarf að ganga.

Dæmi

Inntak 1

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

Úttak 1

0
10
6
8

Athugasemd

Í fyrsta sýnidæminu fjarflytur Little Cyan Fish sig heim til sín í stöðu $0$, svo hann þarf ekkert að ganga.

Í öðru sýnidæminu gengur hann frá $0$ til $10$ og færir heimili sitt í stöðu $5$ á leiðinni. Síðan fjarflytur hann sig í stöðu $5$. Heildarvegalengdin er $10$.

Í þriðja sýnidæminu gengur hann frá $0$ til $4$ og færir heimili sitt í stöðu $2$ á leiðinni. Síðan fjarflytur hann sig í $2$ og gengur í $0$. Heildarvegalengdin er $4 + 2 = 6$.

Í fjórða sýnidæminu fjarflytur hann sig í $0$, gengur í $3$ og færir heimili sitt í $3$. Síðan gengur hann í $-2$ og fjarflytur sig í $3$. Heildarvegalengdin er $3 + 5 = 8$.