Tối ưu hóa đóng gói

Trong một buổi thảo luận về tối ưu hóa quy trình, FullHouse Dev và đồng nghiệp được đưa ra một bài toán thú vị về đóng gói hàng hóa. Họ cần tìm cách giảm thiểu số lượng gói hàng cần vận chuyển bằng cách đặt các gói nhỏ vào trong các gói lớn hơn. Với tinh thần làm việc nhóm, họ bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev và đồng nghiệp nhận được \(N\) gói hàng, mỗi gói có một giá trị \(X\) đại diện cho kích thước của nó. Một gói hàng có thể đặt vào trong một gói khác nếu và chỉ nếu \(X_i < X_j\), và mỗi gói chỉ có thể chứa tối đa một gói khác. Nhiệm vụ của họ là xác định số lượng gói hàng tối thiểu cần thiết sau khi tối ưu hóa việc đóng gói.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng bộ test.
• Với mỗi bộ test:
  • Dòng đầu tiên chứa số nguyên \(N\) - số lượng gói hàng.
  • \(N\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(X\) - kích thước của mỗi gói hàng.

OUTPUT FORMAT:

• Với mỗi bộ test, in ra một số nguyên duy nhất - số lượng gói hàng tối thiểu sau khi tối ưu hóa.

Ràng buộc:

• \(1 \leq T \leq 1000\)
• \(1 \leq N \leq 100000\)
• \(1 \leq X \leq 1000000000\)

Ví dụ

INPUT

3
3
1
2
3
4
2
2
2
2
3
11
111
1111

OUTPUT

1
4
1

Giải thích

• Bộ test #1: Có thể đặt gói kích thước 1 vào gói kích thước 2, sau đó đặt gói kích thước 2 (đã chứa gói kích thước 1) vào gói kích thước 3. Kết quả là chỉ còn 1 gói.
• Bộ test #2: Cả 4 gói đều có kích thước bằng nhau nên không thể đặt gói nào vào gói nào. Kết quả là vẫn còn 4 gói.
• Bộ test #3: Có thể đặt gói kích thước 11 vào gói kích thước 111, sau đó đặt gói kích thước 111 (đã chứa gói kích thước 11) vào gói kích thước 1111. Kết quả là chỉ còn 1 gói.