(pair.*)

Cho số nguyên dương \(N\). Có thể coi \(N\ = \ a_{1},a_{2},\ \ldots,\ a_{m}\) \((0 \leq a_{i} \leq 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.

Dữ liệu vào:

• Dòng đầu tiên chứa \(T\) là số test cần thực hiện \((1\ \leq \ T\ \leq \ 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 \times 10}^{5}\).

Kết quả:

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

Ví dụ:

Giải thích:

• Với test số 1 ta có thể thực hiện thay đổi như sau: Đổi vị trí 2 và 3, đổi vị trí 4 và 5, đổi vị trí 5 và 6.

• Với test số 2 ta không thực hiện thay đổi được vì các vị trí toàn là số lẻ.

• Với test số 3 thay đổi vị trí 3 và 4, tiếp theo đổi vị trí 2, 3, tiếp theo đổi vị trí 4 và 5, tiếp theo đổi vị trí 3, 4 ta được kết quả.

Ràng buộc:

• Có 30% test tương ứng 30% số điểm có \(T\ = \ 1,\ N\ \leq \ 10^{6}\).

• Có 30% test tương ứng 30% số điểm có \(T\ \leq \ 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.