A monoalphabetic substitution cipher assigns one uppercase English letter to each uppercase English letter, then replaces every letter of a word with its assigned letter. A word before encryption is called a plaintext word, and a word after encryption is called a ciphertext word.
The substitution must satisfy both of the following conditions.
A letter may be replaced with itself. The order of the letters and the length of the word do not change.
For example, assigning X to A and Y to B turns ABBA into XYYX. Turning ABBA into XYYY is impossible because the two occurrences of A would be replaced with different letters. Turning ABBA into XXXX is also impossible because the different letters A and B would be replaced with the same letter.
Dadas knows a ciphertext consisting of words and a plaintext word expected to occur frequently in the ciphertext. However, Dadas does not know the substitution.
A word is a candidate word if some substitution satisfying the rules above can turn into that word. Each word is checked independently: different candidate words may use different substitutions.
Dadas counts the occurrences of each candidate word in the ciphertext and guesses that the most frequent candidate word is the encrypted form of . If several candidate words have the same highest frequency, Dadas chooses the lexicographically smallest one. To compare two words lexicographically, find their first differing letters from the left; the word whose letter comes earlier in the alphabet is smaller. For example, if ABCA and XYZX are candidates occurring twice each, Dadas chooses ABCA.
Given the ciphertext and , find the word Dadas chooses. If there are no candidate words, output -1.
The input is given in the following format.
For each test case, output the word Dadas chooses on a separate line. If there are no candidate words, output -1.
In the first test case, the candidate ABCA occurs times and the candidate XYZX occurs times. QQQQ is not a candidate, so Dadas chooses ABCA.
In the second test case, the candidates are XQXR and ZAZB. They occur times and time, respectively, so Dadas chooses XQXR.
In the third test case, both candidates ABCA and XYZX occur times. ABCA is lexicographically smaller, so Dadas chooses ABCA.
is the number of test cases. Each test case is given in the following format.
is the -th ciphertext word (). A word may appear multiple times, and every occurrence is counted.
| 2 | 31 | . |
| 3 | 56 | No additional constraints. |
In the fourth test case, has length , but every ciphertext word has length . There are no candidates, so the output is -1.
