THE PROBLEM STATEMENT:

Emma wants to send a file containing a secret message over the internet. The probability that the file will be intercepted is very less but Emma is not willing to take any chance. So, she decides that she will encrypt the file. She asks her friend Robert for help, who is an expert in the field of cryptography. Robert gives a cipher to help Emma.

The cipher is a follows: The frequency of each character is found. The character with the largest frequency is replaced with the character with the least frequency. If the characters have same frequency, then the character with the higher ASCII value is assumed to be having the higher frequency.
Emma wrote a code for encryption of the original message but the message was encrypted wrongly by her code, as at the destination, the original message couldn't be retrieved.

Your task is simple, write a code for encrypting Emma's message

INPUT:
The first line of input consists of the number of test cases t. Then t lines follow, each line contains a different message E to be encrypted.

OUTPUT:
The output contains t lines, one for each test case, containing the encrypted message for that particular test case.

CONSTRAINTS:
1<=t<=30
1<=|E|<=10000
String E may contain upper case characters('A' - 'Z'), space(' ') and dot('.') character.