Trong vườn nhà Bin có \(n\) con khỉ sống trong \(n\) tòa tháp được xếp liên tiếp nhau trên một đường thẳng, các tòa tháp được đánh số từ \(1\) đến \(n\). Chiều cao của tòa tháp thứ \(i\) là \(h_{i}\) mét.

Mỗi tòa tháp đều có duy nhất một cửa sổ nhỏ ở tầng trên cùng để quan sát. Con khỉ ở toà tháp \(i\) sẽ chỉ nhìn thấy con khỉ khác ở tòa tháp \(j\) nếu độ cao hai tòa tháp này bằng nhau \((h_{i} = h_{j})\) và mọi tòa tháp ở giữa đều thấp hơn hai tòa tháp này (\(h_{k} < h_{i} \forall \min(i, j) < k < \max(i, j)\)).

Để tránh việc một số con khỉ trở nên cô đơn và nổi loạn, mỗi con khỉ cần phải nhìn thấy một con khỉ khác để có thể giao tiếp. Bin muốn chia \(n\) con khỉ thành \(\dfrac{n}{2}\) cặp, sao cho các con khỉ được ghép cặp có thể nhìn thấy nhau và mỗi con khỉ được ghép với đúng một con khỉ khác.

Bin nhận thấy rằng với các tòa tháp hiện tại thì có thể không tồn tại cách ghép cặp nào cho các con khỉ thỏa mãn yêu cầu kể trên. Tuy nhiên, cậu có thể thực hiện một số thao tác để thay đổi chiều cao của các tòa nhà. Mỗi thao tác Bin có thể chọn nâng một tòa tháp thêm độ cao \(1\) mét.

Hãy giúp Bin tính số thao tác ít nhất cần thiết sao cho tồn tại cách để có thể ghép cặp cho các con khỉ.

Input

• Dòng đầu tiên gồm một số nguyên \(T\) là số bộ test. \(T\) nhóm dòng sau, mỗi nhóm dòng thể hiện một test:
  • Dòng đầu gồm một số nguyên dương \(n\) \((1 \leq n \leq 3 \times 10^{5})\). Dữ liệu đảm bảo \(n\) luôn chẵn.
  • Dòng thứ hai gồm \(n\) số nguyên \(h_{1}, h_{2}, \ldots, h_{n}\) \((1 \leq h_{i} \leq 10^{9})\).
• Dữ liệu đảm bảo \(N \leq 3 \times 10^{5}\), với \(N\) là tổng các giá trị \(n\) trong tất cả các bộ test.

Output

• Gồm \(T\) dòng, dòng thứ \(i\) gồm một số duy nhất là kết quả của test thứ \(i\).

Scoring

• Subtask \(1\) (\(21\%\) số điểm): \(N \leq 30\).
• Subtask \(2\) (\(23\%\) số điểm): \(N \leq 300\).
• Subtask \(3\) (\(27\%\) số điểm): \(N \leq 1000\).
• Subtask \(4\) (\(29\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
4
1 3 6 2
8
4 5 1 4 1 3 6 6
18
2 4 5 2 1 1 4 6 3 5 3 6 5 4 3 5 3 6

6
6
14