Bigger is Greater

Find the lexicographically smallest string greater than w by rearranging its letters (next permutation algorithm). If no such string exists, return 'no answer'. Algorithm: (1) Find the rightmost position i where w[i-1] < w[i]. (2) Find the rightmost position j where w[j] > w[i-1]. (3) Swap w[i-1] and w[j]. (4) Reverse the suffix from position i to the end. Example: 'hefg' → find pivot at 'e' (position 1) → swap 'e' with 'g' → 'hgef' → reverse suffix 'ef' → 'hegf'

Input

First line: T (number of test cases). Next T lines: each contains a string w.

Output

For each test case, output the next lexicographically greater string or 'no answer'.

Sample

5
ab
bb
hefg
dhck
dkhc

Expected

ba
no answer
hegf
dhkc
hcdk