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 ≤ 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, …, h_N~ ~(h_i ≤ 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 ≤ 100~

Subtask 2: ~30~% số test thỏa mãn ~N ≤ 1000~

Subtask 3: ~40~% số test thỏa mãn ~N ≤ 100000~