Little Cyan Fish está en una recta numérica. Inicialmente, se encuentra en la posición $a_0$, y su casa está en la posición $0$.

Quiere visitar las posiciones $a_1, a_2, \ldots, a_n$ en este orden. Puede caminar en cualquier dirección a lo largo de la recta numérica. En cualquier momento, puede teletransportarse a su casa o mover su casa a su posición actual. Ambas acciones son gratuitas y pueden realizarse cualquier número de veces, incluso mientras está caminando.

Halla la distancia total mínima que necesita caminar para visitar todas las posiciones en el orden dado.

Entrada

Hay múltiples casos de prueba. La primera línea de la entrada contiene un solo entero $T$ ($1 \le T$), que indica el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene un solo entero $n$ ($1 \le n \le 5 \times 10^5$), que indica el número de posiciones a visitar. La segunda línea contiene $n + 1$ enteros $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), que indican la posición inicial y las posiciones a visitar.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $5 \times 10^5$.

Salida

Para cada caso de prueba, imprime una sola línea con un único entero, que indique la distancia total mínima que Little Cyan Fish necesita caminar.

Ejemplos

Entrada 1

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

Salida 1

0
10
6
8

Nota

En el primer caso de prueba de ejemplo, Little Cyan Fish se teletransporta a su casa en la posición $0$, por lo que no necesita caminar.

En el segundo caso de prueba de ejemplo, camina de $0$ a $10$ y mueve su casa a la posición $5$ en el camino. Luego se teletransporta a la posición $5$. La distancia total es $10$.

En el tercer caso de prueba de ejemplo, camina de $0$ a $4$ y mueve su casa a la posición $2$ en el camino. Luego se teletransporta a $2$ y camina hasta $0$. La distancia total es $4 + 2 = 6$.

En el cuarto caso de prueba de ejemplo, se teletransporta a $0$, camina hasta $3$ y mueve su casa a $3$. Luego camina hasta $-2$ y se teletransporta a $3$. La distancia total es $3 + 5 = 8$.