Cặp số chẵn lẻ

Cho số nguyên dương $N$. Có thể coi $N = a_1a_2 \dots a_m$ $(0 \le a_i \le 9, i = 1..m)$ tức là số nguyên dương $N$ có $m$ chữ số. Người ta có thể thực hiện thay đổi các cặp số $(a_i, a_{i+1})$ nếu hai số $a_i$ và $a_{i+1}$ là cặp số chẵn lẻ hoặc cặp số lẻ chẵn.

Ví dụ: $N = 152984$ ta có thể thực hiện thay đổi như sau:

• Thực hiện đổi vị trí thứ 2 $(a_2 = 5)$ và vị trí 3 $(a_3 = 2)$ cho nhau ta được số 125984.
• Thực hiện thay đổi vị trí 4 $(a_4 = 9)$ và vị trí 5 $(a_5 = 8)$ cho nhau ta được 125894.

Tuy nhiên, với $N = 152984$ ta không thể thay đổi vị trí 1 $(a_1 = 1)$ và vị trí 2 $(a_2 = 5)$ vì nó đều là cặp số lẻ.

Yêu cầu: Tìm số nhỏ nhất có thể tạo ra sau khi thực hiện một số lần liên tiếp các phép biến đổi cặp số như trên.

Đọc vào từ file PAIR.INP gồm:

• Dòng đầu tiên chứa $T$ là số test cần thực hiện $(1 \le T \le 1000)$.
• $T$ dòng tiếp theo mỗi dòng ghi số nguyên $N$.
• Dữ liệu đảm bảo tổng của tất cả số chữ số của $N$ không vượt quá $3.10^5$.

Ghi ra file PAIR.OUT mỗi dòng tương ứng với giá trị tìm được của đề bài.

• Có 30% test tương ứng 30% số điểm có $T = 1, N \le 10^6$.
• Có 30% test tương ứng 30% số điểm có $T \le 100$ và $N$ có độ dài không quá $10^2$.
• Có 40% test khác tương ứng 40% số điểm có $N$ ứng với các trường hợp còn lại.