Số nhỏ nhất

Cho số nguyên dương \(n\). Có thể coi \(n = a_1a_2...a_m\) (\(0 \le a_i \le 9\)) tức là số nguyên dương \(n\) có \(m\) chữ số.
Người ta có thể thực hiện đổi chỗ hai chữ số kề cận nhau (tức là đổi chỗ \(a_i\) cho \(a_{i+1}\)) nếu hai chữ số đó tạo thành một cặp số chẵn lẻ hoặc lẻ chẵn.

Yêu cầu: Hãy thực hiện một số thao tác đổi chỗ các chữ số kề cận nhau của số nguyên dương \(n\) theo cách trên (nếu có thể) để sau khi đổi chỗ ta được số có giá trị nhỏ nhất, trường hợp không thể đổi chỗ vẫn giữ nguyên \(n\).

Input

Dữ liệu vào: Từ tệp văn bản SNN.INP ghi theo cấu trúc sau:

Dòng đầu ghi số bộ test \(t\) (\(0 < t \le 10^3\)).
Dòng thứ hai ghi \(t\) số nguyên dương \(n\) (\(0 < n \le 10^6\)).

Output

Dữ liệu ra: Ghi vào tệp văn bản SNN.OUT ghi \(t\) dòng, mỗi dòng là một số \(n\) nhỏ nhất tìm được.

Example

Test 1

Input

2
54321
7531

Output

42531
7531

Note

Số thứ nhất : 54321

Xét cặp chữ số 5 và 4 là cặp lẻ chẵn và 4 < 5 nên đổi chỗ lần 1 ta được số 45321.

Xét cặp chữ số 5 và 3 đều là số lẻ nên không đổi chỗ.

Xét cặp chữ số 3 và 2 là cặp số lẻ chẵn và 2 < 3 nên đổi chỗ lần 2 ta được số 45231.

Xét cặp chữ số 5 và 2 là cặp lẻ chẵn và 2 < 5 nên đổi chỗ lần 3 ta được số 42531.

Xét các cặp số từ trái sang phải không thể đổi chỗ nữa ta được số nhỏ nhất sau khi đổi chỗ là 42531.

Số thứ hai : 7531

Số này không thỏa mãn điều kiện đổi chỗ nên vẫn giữ nguyên.

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Bình luận