Trò chơi rỗng

Trong một buổi giao lưu với các cao thủ lập trình, FullHouse Dev được thách thức giải quyết một bài toán đầy thú vị. Họ phải tìm cách làm rỗng một mảng bằng cách thực hiện các bước di chuyển thông minh. Với tinh thần quyết tâm, FullHouse Dev đã bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) có độ dài \(n\). Trong mỗi lượt, họ có thể chọn một số nguyên \(x\) và thực hiện một trong các thao tác sau:

1. Chọn một chỉ số \(i\) sao cho \(A[i] = x\) và xóa \(A[i]\).
2. Chọn hai chỉ số \(i\) và \(j\) sao cho \(A[i] = A[j] = x\) và xóa cả \(A[i]\) và \(A[j]\) khỏi mảng.

Nhiệm vụ của nhóm là tìm số lượt di chuyển tối thiểu cần thiết để làm cho mảng trở nên rỗng.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Dòng đầu tiên của mỗi test case chứa số nguyên \(n\) - độ dài của mảng.
• Dòng thứ hai của mỗi test case chứa \(n\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• Với mỗi test case, in ra số lượt di chuyển tối thiểu cần thiết để làm cho mảng trở nên rỗng.

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)
• Tổng của \(n\) trong tất cả các test case không vượt quá \(10^6\)

Ví dụ

INPUT

2
4
1 3 5 2
2
6 7

OUTPUT

2
1

Giải thích

• Ở test case đầu tiên:

  1. FullHouse Dev chọn \(x = 1\). Xóa \(A[0]\) và \(A[3]\). Mảng còn lại là \([3, 5]\).
  2. Chọn \(x = 3\). Xóa \(A[0]\) và \(A[1]\). Mảng trở nên rỗng. Vì vậy, số lượt di chuyển tối thiểu là 2.

• Ở test case thứ hai:

  1. FullHouse Dev chọn \(x = 6\). Xóa \(A[0]\) và \(A[1]\). Mảng trở nên rỗng. Vì vậy, số lượt di chuyển tối thiểu là 1.