Guess the Word

Interview

Time limit1sMemory limit128 MB

Summary

Given each uppercase word, output the next distinct arrangement of its letters in dictionary order, or the word itself when it is already last.

Level: Medium4 of 10
Topics: String, Sorting
Solved: No attempts yet

Problem

Sorting every word that can be built from the letters of BEER into dictionary order gives this list.

BEER
BERE
BREE
EBER
EBRE
EEBR
EERB
ERBE
EREB
RBEE
REBE
REEB

In that order the word right after BEER is BERE. Given a word, write a program that sorts every word built from its letters into dictionary order and reports the word that comes right after the given one.

Input

The first line has the number of test cases $T$ ( $1 \le T \le 10$ ). Each test case is one word on a line of its own. A word consists only of the uppercase letters A to Z and holds no spaces. A word is at most 100 letters long.

Output

For each test case, print the word that comes right after the given word, one per line. If the given word is the last one in dictionary order, print the given word unchanged.

Examples1

Example 1

Input

4
HELLO
DRINK
SHUTTLE
ZOO

Expected output

HELOL
DRKIN
SLEHTTU
ZOO