小A和小B在玩字符串游戏。有一个仅由小写英文字母组成字符串str，每人每次能选择字符串里的一个下标，把它改成一个新的字符（必须修改且不能与原来的字符相同）；被选择过的下标不能再次选择。

游戏中，小A的目标是：使得新字符串字典序更小；小B的目标是使得新字符串字典序更大。

众所周知，小A和小B都足够聪明，她们每次修改都会选择最优的方案。那么，游戏结束后，str被修改为？

第一行，一个数字t，表示数据组数。

每组数据一行，一个字符串str。每个字符串仅含有a~z之间的字符。

对于100%的数据：

1\le t \le 1000；

1 \le |str| 50，即字符串str的长度（所含字符数）最少1个最多50个。

每组数据输出一行一个字符串，表示游戏结束时的结果。