Next Permutation

You are given a string s and your task is to find the next lexicographical permutation of s. In other words, find the smallest string greater than s that can be obtained by rearranging its letters. If no such permutation exists, output "no answer".

Formally, given a string \(s\) with characters \(s_0, s_1, \dots, s_{n-1}\), find a permutation \(p\) of \(s\) such that:

[ p > s \quad \text{and} \quad \forall q ; (q > s \Rightarrow p \le q) ]

Input consists of multiple test cases. Each test case is a single string for which you are to compute the next permutation. Use stdin for input and stdout for output.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a single string \(s\) which needs to be processed.

outputFormat

For each test case, output the next lexicographical permutation of the input string on a new line. If no such permutation exists, output "no answer".

## sample

6
ab
bb
abc
xyz
a
ba

ba
no answer
acb
xzy
no answer
no answer

</p>