Cho một 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 đãy này phải được sắp xếp theo trật tự không giảm trước khi in ra.

Đầu vào
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 \(A\).

Đầu ra
Ứ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ẻ, xem ví dụ để rõ hơn định dạng đầu ra.

Ràng buộc
● \(1≤ T≤100\)
● \(1≤N≤105\)
● \(0 ≤A[i] ≤ 10^5\), \(i = 1 .. N\)

input

2
7
12  34  45  9  8  90  3
5
0  1  2  3  4

output

8  12  34  90  3  9  45
0  2  4  1  3