Little Cyan Fish сан өсінде тұр. Бастапқыда ол $a_0$ орнында, ал оның үйі $0$ орнында орналасқан.

Ол $a_1, a_2, \ldots, a_n$ орындарына осы ретпен барғысы келеді. Ол сан өсінің бойымен кез келген бағытта жүре алады. Кез келген уақытта ол өз үйіне телепортациялана алады немесе үйін өзінің ағымдағы орнына көшіре алады. Екі әрекет те тегін және оларды кез келген рет, соның ішінде жүріп бара жатқан кезде де орындауға болады.

Барлық орындарға берілген ретпен бару үшін оған жаяу жүру керек болатын ең аз жалпы қашықтықты табыңыз.

Кіріс деректер

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші жолында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін бірінші жолда бару керек орындардың санын білдіретін бір бүтін сан $n$ ($1 \le n \le 5 \times 10^5$) берілген. Екінші жолда бастапқы орынды және бару керек орындарды білдіретін $n + 1$ бүтін сан $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) берілген.

Барлық тест жағдайлары бойынша $n$ мәндерінің қосындысы $5 \times 10^5$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін Little Cyan Fish жаяу жүруі керек ең аз жалпы қашықтықты білдіретін бір бүтін саннан тұратын бір жолды шығарыңыз.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

0
10
6
8

Ескертпе

Бірінші мысалдағы тест жағдайында Little Cyan Fish $0$ орнындағы үйіне телепортацияланады, сондықтан оған жаяу жүрудің қажеті жоқ.

Екінші мысалдағы тест жағдайында ол $0$ орнынан $10$ орнына дейін жүріп, жол-жөнекей үйін $5$ орнына көшіреді. Содан кейін ол $5$ орнына телепортацияланады. Жалпы қашықтық — $10$.

Үшінші мысалдағы тест жағдайында ол $0$ орнынан $4$ орнына дейін жүріп, жол-жөнекей үйін $2$ орнына көшіреді. Содан кейін ол $2$ орнына телепортацияланып, $0$ орнына дейін жүреді. Жалпы қашықтық — $4 + 2 = 6$.

Төртінші мысалдағы тест жағдайында ол $0$ орнына телепортацияланып, $3$ орнына дейін жүреді де, үйін $3$ орнына көшіреді. Содан кейін ол $-2$ орнына дейін жүріп, $3$ орнына телепортацияланады. Жалпы қашықтық — $3 + 5 = 8$.