Next Permutation

Given a string s, your task is to compute its lexicographically next permutation. More formally, find the smallest permutation s' such that $$ s' > s $$ in lexicographical order. If no such permutation exists, output no answer.

For example, if s is "ab", then the next permutation is "ba", and if s is "bb", there is no answer.

inputFormat

The first line contains a single integer T representing the number of test cases. Each of the following T lines contains a non-empty string s.

outputFormat

For each test case, print the lexicographically next permutation of s on a new line. If such permutation does not exist, print no answer.## sample

3
ab
bb
hefg

ba
no answer
hegf