You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Em là chú cá voi chưa gặp được anh đã rơi xuống biển sâu thăm thẳm.

Anh như ngang qua, lại chẳng nghe thấy hơi thở của em.

Người ta thường gọi chú cá voi 52 Hz là chú cá voi cô đơn nhất hành tinh, bởi tiếng kêu của nó có tần số 52 Hz, cao hơn nhiều so với những chú cá voi khác, không thể giao tiếp được.

Trong cuộc sống, nhiều người cũng tin rằng, những người có cùng “tần số” thì sẽ đến với nhau một cách tự nhiên.

Ở thế giới nọ, “tần số” của mỗi người được biểu thị qua một con số nguyên dương. Nếu “tần số” của hai người bằng nhau, thì hai người đó là bạn của nhau. Nếu hai người cùng là bạn của một người khác, thì hai người đó cũng là bạn của nhau. Một nhóm bạn là một nhóm người đôi một là bạn của nhau. Một người cũng được coi là một nhóm bạn.

Yêu cầu

Cho $T$ test. Với mỗi test: cho $n$ số $a_1,\dots,a_n$ biểu thị “tần số” của $n$ người. Hãy chia toàn bộ $n$ người thành hai nhóm bạn (theo cách hiểu về nhóm bạn nêu trên) sao cho:

• tổng tần số của mỗi nhóm là số chẵn; và
• chênh lệch giữa tổng tần số của hai nhóm là nhỏ nhất có thể.

Hiển nhiên, mỗi nhóm phải có ít nhất 1 người.

Dữ liệu

Vào từ đầu vào chuẩn:

• Dòng 1: số nguyên dương $T$ ($T \le 2000$) — số test.
• Với mỗi test:
  • Dòng đầu: số nguyên dương $n$.
  • Dòng tiếp: $n$ số nguyên dương $a_1,\dots,a_n$.

Kết quả

Với mỗi test, ghi ra một dòng chứa một số nguyên dương là chênh lệch tối thiểu giữa hai nhóm; trường hợp không thể chia, ghi -1.

Ví dụ

2
6
6 3 3 6 3 3
13
13 12 11 10 9 8 7 6 5 4 3 2 1

0
-1

Giới hạn

Subtask 1 (40% số điểm): $\sum n \le 10^3$, $a_i \le 10^6$;

Subtask 2 (10% số điểm): $\sum n \le 10^6$, $a_i \le 10^6$;

Subtask 3 (10% số điểm): $\sum n \le 10^6$, $a_i \le 10^9$;

Subtask 4 (40% số điểm): $\sum n \le 5\times 10^6, a_i \le 10^9$.

$\sum n$ là tổng các $n$ tính trên toàn bộ một input.