Phép biến đổi vĩ đại

Cho một mảng $a$ gồm $n$ số nguyên. Bạn được phép thực hiện thao tác sau không hoặc nhiều lần:

• Chọn hai vị trí $i\ne j$ sao cho $a_i\ne a_j$ (hai giá trị phải khác nhau);
• Xoá đồng thời phần tử thứ $i$ và phần tử thứ $j$ khỏi mảng.

Sau mỗi thao tác, mảng ngắn đi $2$ phần tử và các phần tử còn lại giữ nguyên thứ tự tương đối.

Hãy tìm kích thước nhỏ nhất của mảng sau khi thực hiện một dãy thao tác tuỳ ý.

Ví dụ với $n=6$ và $a=[1,6,1,1,4,4]$, ta có thể:

• Chọn $i=1,j=5$ (giá trị $1$ và $4$), mảng trở thành $[6,1,1,4]$;
• Chọn $i=1,j=2$ (giá trị $6$ và $1$), mảng trở thành $[1,4]$;
• Chọn $i=1,j=2$ (giá trị $1$ và $4$), mảng trở thành rỗng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên $n$ là độ dài mảng $a$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng kích thước nhỏ nhất có thể của mảng sau khi thực hiện các thao tác.

Ràng buộc

• $1\le t\le {10}^4$
• $1\le n\le 2·{10}^5$
• $1\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2·{10}^5$.

Ví dụ