Sắp xếp theo chẵn lẻ bit

Trong một buổi phỏng vấn tại công ty, FullHouse Dev được giao một bài toán thú vị về xử lý bit. Họ cần phải viết một thuật toán sắp xếp đặc biệt dựa trên số lượng bit 1 trong biểu diễn nhị phân của các số.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) gồm \(n\) số nguyên. Nhiệm vụ của họ là sắp xếp lại mảng theo các điều kiện sau:

1. Các số có số lượng bit 1 chẵn sẽ 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ũng đượ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 \(n\) số nguyên của mảng \(A\)

OUTPUT FORMAT:

• Với mỗi test case, in ra mảng đã được sắp xếp theo yêu cầu 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ả [5, 6, 12, 2, 7, 8] được sắp xếp như sau:

• 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)