F. Exchange
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a string of lowercase English letters. You are allowed to choose two letters that exist in any position in the string, replace all occurrences of the first letter you chose with the second one, and replace all occurrences of the second letter you chose with the first one.

Your task is to find the string that comes first in dictionary order among all possible strings that you can get by performing the above operation at most once.

For example, by exchanging letter ‘a’ with letter ‘h’ in string “hamza”, we can get string “ahmzh”.

Input

The first line of input contains a single integer T, the number of test cases.

Each test case contains a non-empty string on a single line that contains no more than 105 lowercase English letters.

Output

For each test case, print the required string on a single line.

Example
Input
3
hamza
racecar
mca
Output
ahmzh
arcecra
acm