Cắt trái cây

Trong một buổi picnic, FullHouse Dev được giao nhiệm vụ cắt trái cây cho cả nhóm. Họ nhận ra rằng việc cắt trái cây có cùng trọng lượng cùng một lúc sẽ tiết kiệm thời gian hơn. Với tinh thần làm việc hiệu quả, FullHouse Dev bắt đầu lên kế hoạch cắt trái cây một cách tối ưu.

Bài toán

FullHouse Dev được cung cấp một mảng \(W\) đại diện cho trọng lượng của \(n\) trái cây. Trong mỗi bước, họ có thể cắt tất cả các trái cây có cùng trọng lượng. Nhiệm vụ của nhóm là xác định số bước tối thiểu cần thực hiện để cắt hết tất cả trái cây.

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\) - số lượng trái cây.
• Dòng tiếp theo của mỗi test case chứa \(n\) số nguyên - trọng lượng của các trái cây.

OUTPUT FORMAT:

• Với mỗi test case, in ra số bước tối thiểu cần thực hiện để cắt hết tất cả trái cây.

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq W[i] \leq 10^9\)

Ví dụ

INPUT

2
6
20 40 30 50 40 20
4
3 6 7 7

OUTPUT

4
3

Giải thích

• Ở test case đầu tiên, FullHouse Dev có thể cắt trái cây theo các bước sau:

  1. Cắt trái cây có trọng lượng 20 (vị trí 1 và 6)
  2. Cắt trái cây có trọng lượng 40 (vị trí 2 và 5)
  3. Cắt trái cây có trọng lượng 30 (vị trí 3)
  4. Cắt trái cây có trọng lượng 50 (vị trí 4) Tổng cộng cần 4 bước.

• Ở test case thứ hai, nhóm có thể cắt trái cây theo các bước sau:

  1. Cắt trái cây có trọng lượng 7 (vị trí 3 và 4)
  2. Cắt trái cây có trọng lượng 3 (vị trí 1)
  3. Cắt trái cây có trọng lượng 6 (vị trí 2) Tổng cộng cần 3 bước.