Problem Statement:

Tom is a very talented photographer; he has his own Facebook photography page with many likes and followers.

Although Tom became famous he never forgot his friends; when a group of friends wants to take a photo, Tom (as a professional) first assign a decimal digit (1-9) for each person repressing his height in some kind of photographers units.

Tom needs to take photos in every possible order of the people considering the heights (it?s also a photographer?s thing) i.e. a permutation of the heights.

We can describe the order of these people (heights in particular) using a string of decimal digits.

In the first photo he puts people in order that the value of the describing string as a decimal number is the smallest possible. In the next photo he puts people in order that the value of the describing string as a decimal number is the next smallest possible. And he keep repeating the last step until he reaches the value of the describing string as a decimal number is biggest possible, when he finishes that, he is done taking photos of these group of people, Photography isn?t as easy as you thought!

However, when the number of people is big, the task become very hard. Especially that tom isn?t good at math as much as he is good at photography.

So you need to help Tom take the next photo, he gives you the current order (permutation) of the heights and you give him the order for the next photo or you tell him that he?s finally done.

Input Format:

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of test cases that follow. Each test case is a single line that contains up to 100 decimal digits which is the input value.

Output Format:

For each data set there is one line of output. If there is no next photo, the output should be the string ?DONE? without quotes. If there is more photo(s) to take, the output should be next larger permutation of heights.

Sample Input:

3
123
521
279134399742

Sample Output:

132
DONE
279134423799