Cho mảng ~a~ gồm ~2n~ số nguyên. Trong một thao tác, bạn chọn hai phần tử kề nhau ~a_i~ và ~a_{i+1}~, xóa cả hai khỏi mảng và cộng ~|a_i - a_{i+1}|~ vào điểm số. Sau mỗi lần xóa, các chỉ số được đánh lại (hai phần tử hai bên chỗ vừa xóa trở thành kề nhau).

Sau đúng ~n~ thao tác, mảng trở thành rỗng. Hỏi điểm số lớn nhất có thể đạt được là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên ~t~ — số bộ test. Mỗi bộ test gồm hai dòng:

• Dòng thứ nhất chứa số nguyên ~n~.
• Dòng thứ hai chứa ~2n~ số nguyên ~a_1, a_2, \ldots, a_{2n}~ — các phần tử của mảng.

Kết quả

In ra ~t~ dòng, dòng thứ ~i~ là điểm số lớn nhất của bộ test thứ ~i~ sau khi thực hiện đúng ~n~ thao tác.

Ví dụ

Đầu vào:

3
2
42 42 42 42
1
42 69
3
1 2 3 4 5 6

Đầu ra:

0
27
9

Giải thích: Ở bộ test thứ nhất mọi phần tử bằng nhau nên mỗi thao tác đều cho ~0~ điểm.

Ở bộ test thứ hai chỉ có một cách chọn, được ~|42 - 69| = 27~ điểm.

Ở bộ test thứ ba, một cách làm tối ưu: xóa ~3, 4~ (được ~1~ điểm), mảng còn ~[1, 2, 5, 6]~; xóa ~2, 5~ (được ~3~ điểm), mảng còn ~[1, 6]~; xóa ~1, 6~ (được ~5~ điểm). Tổng ~1 + 3 + 5 = 9~.

Giới hạn

• ~1 \le t \le 10^5~
• ~1 \le n \le 2 \cdot 10^5~
• ~0 \le a_i \le 10^9~
• Tổng ~n~ trên tất cả các bộ test không vượt quá ~2 \cdot 10^5~.