Little Cyan Fish se trouve sur une droite numérique. Initialement, il est à la position $a_0$, et sa maison est à la position $0$.

Il souhaite visiter les positions $a_1, a_2, \ldots, a_n$ dans cet ordre. Il peut marcher dans l'une ou l'autre direction le long de la droite numérique. À tout moment, il peut se téléporter chez lui ou déplacer sa maison à sa position actuelle. Ces deux actions sont gratuites et peuvent être effectuées autant de fois qu'il le souhaite, y compris pendant qu'il marche.

Trouvez la distance totale minimale qu'il doit parcourir à pied pour visiter toutes les positions dans l'ordre donné.

Entrée

Il y a plusieurs cas de test. La première ligne de l'entrée contient un seul entier $T$ ($1 \le T$), indiquant le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un seul entier $n$ ($1 \le n \le 5 \times 10^5$), indiquant le nombre de positions à visiter. La deuxième ligne contient $n + 1$ entiers $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), indiquant la position initiale et les positions à visiter.

Il est garanti que la somme de $n$ sur tous les cas de test ne dépasse pas $5 \times 10^5$.

Sortie

Pour chaque cas de test, affichez une seule ligne contenant un seul entier, indiquant la distance totale minimale que Little Cyan Fish doit parcourir à pied.

Exemples

Entrée 1

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

Sortie 1

0
10
6
8

Remarque

Dans le premier cas de test de l'exemple, Little Cyan Fish se téléporte chez lui à la position $0$, il n'a donc pas besoin de marcher.

Dans le deuxième cas de test de l'exemple, il marche de $0$ à $10$ et déplace sa maison à la position $5$ en chemin. Il se téléporte ensuite à la position $5$. La distance totale est de $10$.

Dans le troisième cas de test de l'exemple, il marche de $0$ à $4$ et déplace sa maison à la position $2$ en chemin. Il se téléporte ensuite en $2$ et marche jusqu'en $0$. La distance totale est de $4 + 2 = 6$.

Dans le quatrième cas de test de l'exemple, il se téléporte en $0$, marche jusqu'en $3$ et déplace sa maison en $3$. Il marche ensuite jusqu'en $-2$ et se téléporte en $3$. La distance totale est de $3 + 5 = 8$.