C là người làm công tác khí tượng, đảm nhiệm vai trò đo lường nhiệt độ, áp suất không khí và nhiều thông số khác trên các đỉnh núi. Khu vực mà C được chuyển công tác tới lần này là một dãy núi gồm $N$ ngọn núi liên tiếp nhau. C đánh số các ngọn núi theo thứ tự từ 1 tới $N$ và ngọn núi thứ $i$ có độ cao là $h_i$. C đã lắp đặt $N$ thiết bị đo lường trên $N$ đỉnh núi, mỗi đỉnh núi 1 thiết bị. Để nhận dữ liệu từ các thiết bị này, C cần lắp đặt các thiết bị thu sóng. Tuy nhiên, nền kinh tế đang gặp nhiều khó khăn do đại dịch Covid-19 đã khiến ngân sách trở nên eo hẹp. Vì thế, C chỉ được cung cấp đủ kinh phí để chi trả cho việc lắp đặt đúng 2 thiết bị thu sóng mà thôi. Vì lý do kỹ thuật nên vùng quét của các thiết bị thu sóng không được giao nhau. Do đó, C quyết định chia dãy núi thành 2 nhóm, mỗi nhóm có ít nhất 1 ngọn núi. Nhóm đầu tiên gồm các ngọn núi được đánh số từ $1$ tới $K$, nhóm còn lại gồm các ngọn núi đánh số từ $K+1$ tới $N$. Sau đó, C sẽ đặt một thiết bị thu sóng ở một trong các ngọn núi từ $1$ tới $K$ và nó sẽ được kết nối với tất cả các thiết bị đo lường trên các ngọn núi từ $1$ tới $K$. Thiết bị thu sóng còn lại sẽ được đặt ở một trong các ngọn núi từ $K+1$ tới $N$ và được kết nối với các thiết bị đo lường còn lại. Lượng năng lượng cần thiết cho việc kết nối giữa 1 thiết bị thu sóng và 1 thiết bị đo lường sẽ bằng chênh lệch độ cao giữa vị trí lắp đặt của 2 thiết bị. Cụ thể hơn, lượng năng lượng cần thiết cho việc kết nối thiết bị đo lường ở đỉnh $i$ và thiết bị thu sóng ở đỉnh $j$ sẽ có giá trị là $|h_i-h_j|$. C đương nhiên làm muốn tổng lượng năng lượng cần thiết để kết nối tất cả các thiết bị với nhau là bé nhất. Tuy nhiên, có tới $N-1$ cách chia dãy núi thành 2 nhóm, và với mỗi cách lại có rất nhiều vị trí đặt thiết bị thu sóng khác nhau. Vì thế, với các thông tin về dãy núi mà C cung cấp, bạn hãy giúp anh ấy chọn phương án mà tổng năng lượng cần thiết là nhỏ nhất nhé.

INPUT

• Dòng đầu tiên là $T$ $(T\le 5)$, là số lượng bộ test.
• Dòng đầu tiên của mỗi bộ test là $N$, số lượng ngọn núi.
• Dòng thứ hai của mỗi bộ test gồm $N$ số nguyên dương $h_1,h_2,\dots ,h_N$ $(h_i\le {10}^9)$ là độ cao của các ngọn núi.

OUTPUT

• Gồm $T$ dòng, mỗi dòng là tổng năng lượng nhỏ nhất tương ứng với mỗi bộ test

Ví dụ

Input

3
5
2 4 3 2 5
10
6 9 9 6 6 4 4 4 4 4
2
18 5

Output

3
6
0

Giải thích:

• Ở bộ test 1, ta chọn $K=4$ và đặt 2 thiết bị thu sóng ở vị trí $3$ và $5$. Khi đó tổng năng lượng cần dùng sẽ là $|2-3|+|4-3|+|3-3|+|2-3|+|5-5|=3$.
• Ở bộ test 1, ta có thể chọn $K=3$ và 2 thiết bị thu sóng ở vị trí $2$ và $4$. Khi đó tổng năng lượng cần dùng sẽ là $|2-4|+|4-4|+|3-4|+|2-5|+|5-5|=6$, nhưng đây sẽ không phải là đáp án tối ưu.

Subtask 1: $30$% số test thỏa mãn $N\le 100$

Subtask 2: $30$% số test thỏa mãn $N\le 1000$

Subtask 3: $40$% số test thỏa mãn $N\le 100000$