Next Lexicographical Permutation

This problem requires you to compute the next lexicographical permutation of a given string. In other words, given a string \(s\), you need to find the smallest string greater than \(s\) by rearranging its characters. If no such permutation exists, output no answer.

The algorithm can be summarized as follows:

• Find the largest index \(k\) such that \(s[k] < s[k+1]\). If no such index exists, then the answer is no answer.
• Find the largest index \(l\) greater than \(k\) such that \(s[k] < s[l]\).
• Swap \(s[k]\) and \(s[l]\).
• Reverse the sub-array \(s[k+1]\) to the end of the string.

This procedure yields the next lexicographical permutation.

inputFormat

Input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. Each of the next (T) lines contains a single non-empty string whose next permutation you need to compute.

outputFormat

For each test case, print the next lexicographical permutation of the given string on a new line. If no such permutation exists, print "no answer".## sample

3
abc
cba
ab

acb
no answer
ba