Rearrange String Maintaining Digit Positions

You are given a string S consisting of both alphabetic characters and digits. Your task is to rearrange the alphabetic characters such that they form the lexicographically smallest sequence possible while ensuring that the digits remain in their original positions.

For example, given the string "b2a1c3", after rearranging, it becomes "a2b1c3" because the letters 'a', 'b', 'c' in sorted order replace the letters in the original string while the digits '2', '1', '3' remain fixed in their original positions.

If the string contains only letters or only digits, output the string as-is.

Input/Output Requirement: Read from standard input (stdin) and output the results to standard output (stdout).

inputFormat

The first line contains an integer T, representing the number of test cases. Each of the following T lines contains a single string S that you need to process.

outputFormat

For each test case, output the rearranged string on a new line.## sample

3
b2a1c3
a1b2c
dcba4321

a2b1c3
a1b2c
abcd4321