Smallest Lexicographical String

You are given a string S consisting of lowercase English letters. In one operation, you can choose any character and perform one of the following operations:

• Flip: Reverse the string (although the reversal operation may affect the order, note that the lexicographical order is considered on the whole string).
• Increment: Increment the character (cyclically, so after 'z' comes 'a').

You may perform any number of these operations (including zero) in any order. Your goal is to obtain the lexicographically smallest string possible from S.

Observation: Since the Increment operation cycles every character back to 'a', the lexicographically smallest string that can be achieved is simply a string of 'a's with the same length as S. Hence, regardless of the input string, the answer will be a repeated n times, where n is the length of S.

Your task is to implement a program that reads multiple test cases, and for each test case, outputs the lexicographically smallest string that can be obtained.

inputFormat

The input is given via stdin and has the following format:

T
S1
S2
...
ST

Here, T is an integer representing the number of test cases, and each Si is a non-empty string of lowercase letters.

outputFormat

For each test case, output the lexicographically smallest string that can be obtained by applying any number of operations, printed to stdout. Each result should be printed on a separate line.

## sample

3
ebac
zzz
abc

aaaa
aaa
aaa

</p>