You are given a string \(s\) consisting of numeric digits (0-9) and Latin alphabetic characters ('a'-'z') only.

Your task is to sort the string but it must be sorted in a unique manner because here even characters or digits have higher priority than odd characters or digits. Although, as usual, other characters or digits have the same priority level. Also, digits have higher priority than characters.

For example, \('0'>'1',\ '0'>'5',\ 'a'>'b',\ '1'>'a',\ '3'>'1',\ 'd'>'b', and\ so\ on\).

Input format

1. The first line contains \(t\) denoting the number of test cases.
2. Each of the next \(t\) lines contains a string.

Output format

Print the sorted string for each test case.

Constraints
\(1 \le t \le 100\\ |s| \le 100\)