Sắp xếp chẵn lẻ nhị phân

Trong một buổi chăm sóc vườn rau, FullHouse Dev nhận thấy cách sắp xếp các luống rau theo một quy tắc đặc biệt sẽ giúp việc tưới nước hiệu quả hơn. Điều này khiến họ nghĩ đến một bài toán thú vị về việc sắp xếp các số theo quy luật bit chẵn lẻ.

Bài toán

Cho một mảng \(A\) gồm \(n\) số nguyên. Nhiệm vụ của bạn là sắp xếp lại mảng theo các điều kiện sau và trả về mảng đã sắp xếp:

1. Các số có số lượng bit 1 chẵn xuất hiện trước theo thứ tự tăng dần.
2. Tiếp theo là các số có số lượng bit 1 lẻ được sắp xếp theo thứ tự tăng dần.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Với mỗi test case:
  • Dòng đầu tiên chứa số nguyên \(n\).
  • Dòng thứ hai chứa mảng \(A\) gồm \(n\) số nguyên.

OUTPUT FORMAT:

• Với mỗi test case, in ra mảng đã được sắp xếp theo quy tắc trên trên một dòng mới.

Ràng buộc:

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

Ví dụ

INPUT

1
6
5 2 8 12 7 6

OUTPUT

5 6 12 2 7 8

Giải thích

Với mảng đầu vào [5, 2, 8, 12, 7, 6], kết quả là [5, 6, 12, 2, 7, 8], trong đó:

• Các số có số lượng bit 1 chẵn: 5(101), 6(110), 12(1100)
• Các số có số lượng bit 1 lẻ: 2(10), 7(111), 8(100)