Next Lexicographical Permutation

Given a string s, your task is to compute its next lexicographical permutation. If such a permutation does not exist, output the smallest permutation (i.e. the sorted order).

The lexicographical permutation of a string is defined as the order of words as they appear in a dictionary. For instance, the next permutation of ab is ba, and when the string is in descending order (for example, dcba), the next permutation is the one in ascending order (abcd).

Recall the algorithm:

1. Find the largest index i such that \(s[i] < s[i+1]\). If no such index exists, the permutation is the highest; return the smallest permutation by sorting the characters in ascending order.

2. Find the largest index j greater than i such that \(s[j] > s[i]\).

3. Swap the characters at i and j.

4. Sort the substring from i+1 to the end in ascending order.

This method guarantees that we arrive at the next highest lexicographical order.

inputFormat

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

You can assume that the input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the next lexicographical permutation of the corresponding string. The output should be written to standard output (stdout).

## sample

3
ab
dcba
aabb

ba
abcd
abab

</p>