计算所谓最佳字符串，规则如下，怎么用 C 语言的程序编写的代码设计的思想方法加以正确地实现的方法是什么

Question

Problem Description
Given a string, you use some letters or digits to creat a new string, this new string have three properties.
1. any two adjacent letter aren't the same.
2. the new string have the biggest length.
3. the new string have the biggest lexicographical ordering.

Input
The input consists of multiple test cases. Each test case contain a string, the string is consist of 'a'~'z', 'A' - 'Z' and '0' - '9'. the length of string is not exceed 500.

Output
For each case, print the new string.

Sample Input
2
abaa
001

Sample Output
aba
010