Little Cyan Fish đang ở trên một trục số. Ban đầu, cậu ấy ở vị trí $a_0$, và nhà của cậu ấy ở vị trí $0$.

Cậu ấy muốn đi thăm các vị trí $a_1, a_2, \ldots, a_n$ theo đúng thứ tự này. Cậu ấy có thể đi bộ theo bất kỳ hướng nào dọc theo trục số. Bất cứ lúc nào, cậu ấy cũng có thể dịch chuyển tức thời về nhà của mình hoặc chuyển nhà của mình đến vị trí hiện tại. Cả hai hành động này đều miễn phí và có thể thực hiện bất kỳ số lần nào, kể cả trong lúc cậu ấy đang đi bộ.

Hãy tìm tổng quãng đường ngắn nhất mà cậu ấy cần đi bộ để thăm tất cả các vị trí theo thứ tự đã cho.

Dữ liệu vào

Có nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên duy nhất $T$ ($1 \le T$), cho biết số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu, dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 5 \times 10^5$), cho biết số lượng vị trí cần đi thăm. Dòng thứ hai chứa $n + 1$ số nguyên $a_0, a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), cho biết vị trí ban đầu và các vị trí cần đi thăm.

Dữ liệu đảm bảo rằng tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $5 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên duy nhất, cho biết tổng quãng đường ngắn nhất mà Little Cyan Fish cần đi bộ.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

0
10
6
8

Ghi chú

Trong bộ dữ liệu ví dụ thứ nhất, Little Cyan Fish dịch chuyển tức thời về nhà của mình tại vị trí $0$, vì vậy cậu ấy không cần phải đi bộ.

Trong bộ dữ liệu ví dụ thứ hai, cậu ấy đi bộ từ $0$ đến $10$ và chuyển nhà của mình đến vị trí $5$ trên đường đi. Sau đó cậu ấy dịch chuyển tức thời đến vị trí $5$. Tổng quãng đường là $10$.

Trong bộ dữ liệu ví dụ thứ ba, cậu ấy đi bộ từ $0$ đến $4$ và chuyển nhà của mình đến vị trí $2$ trên đường đi. Sau đó cậu ấy dịch chuyển tức thời đến $2$ và đi bộ đến $0$. Tổng quãng đường là $4 + 2 = 6$.

Trong bộ dữ liệu ví dụ thứ tư, cậu ấy dịch chuyển tức thời đến $0$, đi bộ đến $3$, và chuyển nhà của mình đến $3$. Sau đó cậu ấy đi bộ đến $-2$ và dịch chuyển tức thời đến $3$. Tổng quãng đường là $3 + 5 = 8$.