Problem Statement:-
Dev and Vivek are two gold smugglers who have smuggled hundreds of kilograms of gold into the country. The police and intelligence agents have been chasing them for years but the two had always managed to escape. But this time, an undercover agent, Priyal joined the team and Vivek fell for her and his mistake created chaos. Due to which the police finally caught Vivek and agent Priyal handed over the codes to the police. Dev needs to change the code urgently if needed and he has asked for your help. The original code consisted of only 3 Latin letters, ‘D’, ‘E’, and ‘V’. In order to help them, you have to convert this code into the lexicographically smallest possible code but you can perform only 2 types of operations for completing the job. Help them at the earliest.
You can do the following 2 operations any number of times (possibly 0):-
- You can swap the two adjacent letters if one letter is ‘D’ and the other is ‘E’.
- You can swap the two adjacent letters if one letter is ‘E’ and the other is ‘V’.
NOTE:- You can't swap non-adjacent letters and also you can’t swap ‘D’ and ‘V’.
Input
First-line contains a single integer T number of test cases.
Next T lines contain a string S written by Dev contains only ('D', 'E' and 'V').
Output
Print T lines each contain a single lexicographical minimum possible string you can obtain by using two types of swap described above.
Constraints
- 1 ≤ T ≤ 1000.
- 1 ≤ |S| ≤ 105 (length of the string).
In the first test case, the given string s = "DEV" is already lexicographically minimum so we don't have to do any operation.
In the second test case, the given string s = "EDDVED" and the lexicographically minimum string we can make using the above operations is "DDEEVD".
The series of steps to get the desired string:-
(1-based indexing)
1) Swap s[1] with s[2] (Using operation 1, we can swap 'D' and 'E'). string after applying 1st step = "DEDVED".
2) Swap s[2] with s[3] (Using operation 1, we can swap 'D' and 'E'). string after applying 2nd step = "DDEVED".
3) Swap s[4] with s[5] (Using operation 2, we can swap 'V' and 'E'). string after applying 3rd step = "DDEEVD".
We can't make the string "EDDVED" lexicographically smaller than the string "DDEEVD" therefore the answer is "DDEEVD".
