Little Cyan Fish znajduje się na osi liczbowej. Początkowo znajduje się na pozycji $a_0$, a jego dom znajduje się na pozycji $0$.

Chce odwiedzić pozycje $a_1, a_2, \ldots, a_n$ w podanej kolejności. Może iść w dowolnym kierunku wzdłuż osi liczbowej. W dowolnym momencie może przeteleportować się do swojego domu lub przenieść swój dom na swoją aktualną pozycję. Obie te akcje są darmowe i mogą być wykonywane dowolną liczbę razy, w tym również podczas chodzenia.

Znajdź minimalną łączną odległość, jaką musi przejść pieszo, aby odwiedzić wszystkie pozycje w podanej kolejności.

Wejście

Wejście składa się z wielu przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $T$ ($1 \le T$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$), oznaczającą liczbę pozycji do odwiedzenia. Drugi wiersz zawiera $n + 1$ liczb całkowitych $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), oznaczających pozycję początkową oraz pozycje do odwiedzenia.

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \times 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczym wierszu jedną liczbę całkowitą, oznaczającą minimalną łączną odległość, jaką Little Cyan Fish musi przejść pieszo.

Przykład

Wejście 1

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

Wyjście 1

0
10
6
8

Uwagi

W pierwszym przykładowym przypadku testowym Little Cyan Fish teleportuje się do swojego domu na pozycji $0$, więc nie musi w ogóle chodzić.

W drugim przykładowym przypadku testowym idzie z $0$ do $10$ i po drodze przenosi swój dom na pozycję $5$. Następnie teleportuje się na pozycję $5$. Łączna odległość wynosi $10$.

W trzecim przykładowym przypadku testowym idzie z $0$ do $4$ i po drodze przenosi swój dom na pozycję $2$. Następnie teleportuje się do $2$ i idzie do $0$. Łączna odległość wynosi $4 + 2 = 6$.

W czwartym przykładowym przypadku testowym teleportuje się do $0$, idzie do $3$ i przenosi swój dom do $3$. Następnie idzie do $-2$ i teleportuje się do $3$. Łączna odległość wynosi $3 + 5 = 8$.