Pakistan Team is obsessed with match fixing. Their bookie Asif is writing a letter to them and wants nobody else to be able to read it. They use a simple substitution cipher to encode his message. Each letter in the message is replaced with its corresponding letter in a substitution alphabet. A substitution alphabet is a permutation of all the letters in the original alphabet. In this problem, the alphabet will consist of only lowercase letters ('a'-'z').
For example, if message is "hello" and his cipher maps 'h' to 'q', 'e' to 'w', 'l' to 'e' and 'o' to 'r', the encoded message will be "qweer".
Given the original message, determine the cipher that will produce the encoded string that comes earliest alphabetically. Return this encoded string.

Input
The first line consists of a number t representing the number of test case. Then, t lines follow each containing the message that will be less than 10,000 characters. It will contain only lowercase letters ('a'-'z').

Output
Output the Cipher message for each message.

Example

Input:
2
hello
sachin

Output:
abccd
abcdef

见题面

见题面