Little Cyan Fish si trova su una retta numerica. Inizialmente si trova nella posizione $a_0$, e la sua casa si trova nella posizione $0$.

Vuole visitare le posizioni $a_1, a_2, \ldots, a_n$ in questo ordine. Può camminare in entrambe le direzioni lungo la retta numerica. In qualsiasi momento, può teletrasportarsi a casa sua oppure spostare la sua casa nella sua posizione attuale. Entrambe le azioni sono gratuite e possono essere eseguite un numero qualsiasi di volte, anche mentre sta camminando.

Trova la distanza totale minima che deve percorrere a piedi per visitare tutte le posizioni nell'ordine dato.

Input

Ci sono più casi di test. La prima riga dell'input contiene un singolo intero $T$ ($1 \le T$), che indica il numero di casi di test.

Per ciascun caso di test, la prima riga contiene un singolo intero $n$ ($1 \le n \le 5 \times 10^5$), che indica il numero di posizioni da visitare. La seconda riga contiene $n + 1$ interi $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), che indicano la posizione iniziale e le posizioni da visitare.

È garantito che la somma di $n$ su tutti i casi di test non supera $5 \times 10^5$.

Output

Per ciascun caso di test, stampa una singola riga contenente un singolo intero, che indica la distanza totale minima che Little Cyan Fish deve percorrere a piedi.

Esempi

Input 1

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

Output 1

0
10
6
8

Note

Nel primo caso di test di esempio, Little Cyan Fish si teletrasporta a casa sua nella posizione $0$, quindi non ha bisogno di camminare.

Nel secondo caso di test di esempio, cammina da $0$ a $10$ e sposta la sua casa nella posizione $5$ lungo il tragitto. Poi si teletrasporta nella posizione $5$. La distanza totale è $10$.

Nel terzo caso di test di esempio, cammina da $0$ a $4$ e sposta la sua casa nella posizione $2$ lungo il tragitto. Poi si teletrasporta in $2$ e cammina fino a $0$. La distanza totale è $4 + 2 = 6$.

Nel quarto caso di test di esempio, si teletrasporta in $0$, cammina fino a $3$ e sposta la sua casa in $3$. Poi cammina fino a $-2$ e si teletrasporta in $3$. La distanza totale è $3 + 5 = 8$.