Cho dãy A gồm N số nguyên, hãy tách dãy A[] thành hai dãy, một dãy chứa toàn các phần tử chẵn, dãy kia chứa toàn các phần tử lẻ và hai dãy này được sắp xếp theo trật tự không giảm trước khi in ra.

Dữ liệu

Dòng đầu tiên của đầu vào chứa một số nguyên T biểu thị số bộ dữ liệu cần kiểm tra, trong đó mỗi bộ dữ liệu gồm:

• Dòng đầu chứa số nguyên N
• Dòng thứ hai chứa N số nguyên cách nhau một dấu cách biểu thị các phần tử của dãy A.

Kết quả

• Ứng với mỗi bộ dữ liệu đầu vào, in ra một dòng chứa lần lượt các phần tử của dãy chẵn, sau đó là các phần tử của dãy lẻ.

Ví dụ

Dữ liệu

1
15
2 3 5 6 7 8 4 9 7 9 11 13 14 16 14

Kết quả

2 4 6 8 14 14 16 3 5 7 7 9 9 11 13

Ràng buộc

• ~1≤T≤100~
• ~1≤n≤10^5~
• ~0≤∣Aij ∣≤10^5~