Given a word , rearrange the letters of to construct another word in such a way that is lexicographically greater than . In case of multiple possible answers, find the lexicographically smallest one among them.
Input Format
The first line of input contains , the number of test cases. Each of the next lines contains .
Constraints
- will contain only lower-case English letters and its length will not exceed .
Output Format
For each testcase, output a string lexicographically bigger than in a separate line. In case of multiple possible answers, print the lexicographically smallest one, and if no answer exists, print no answer.
Sample Input
5
ab
bb
hefg
dhck
dkhc
Sample Output
ba
no answer
hegf
dhkc
hcdk
Explanation
- Test case 1:
There exists only one string greater thanabwhich can be built by rearrangingab. That isba. - Test case 2:
Not possible to rearrangebband get a lexicographically greater string. - Test case 3:
hegfis the next string lexicographically greater thanhefg. - Test case 4:
dhkcis the next string lexicographically greater thandhck. - Test case 5:
hcdkis the next string lexicographically greater thandkhc.