Homer 有两个朋友 Alice 和 Bob。两人都是弦乐迷。
有一天,Alice 和 Bob 决定玩一个游戏,字符串 $$$s = s_1 s_2 \dots s_n$$$,长度为 $$$n$$$,由小写英文字母组成。他们轮流移动,爱丽丝率先移动。
在一步棋中,玩家必须选择一个之前没有选择过的索引 $$$i$$$ ($$$1 \leq i \leq n$$$),并将 $$$s_i$$$ 更改为 $$$c \neq s_i$$$ 中的任何其他小写英文字母 $$$c$$$。
当所有索引都被选择后,游戏结束。
Alice的目标是使最终字符串按字典顺序尽可能小,而Bob的目标是使最终字符串按字典顺序尽可能大。两人都是游戏高手,所以总是能以最佳状态玩游戏。荷马不是游戏专家,所以他想知道最后的字符串会是什么。
当且仅当满足以下条件之一时,字符串 $$$a$$$ 按字典顺序小于字符串 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 在字母表中的某个字母比 $$$b$$$ 中的相应字母更早出现。
输入
每个测试包含多个测试用例。第一行包含 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含一个由小写英文字母组成的字符串 $$$s$$$ ($$$1 \leq |s| \leq 50$$$)。
输出
对于每个测试用例,在一行中打印最终字符串。
示例
输入 #1
3 a bbbb az
输出 #1
b azaz by
注意
在第一个测试用例中:Alice 迈出第一步,必须将唯一的字母更改为不同的字母,因此她将其更改为“b”。
在第二个测试用例中:Alice 将第一个字母更改为“a”,然后 Bob 将第二个字母更改为“z”,Alice 将第三个字母更改为“a”,然后 Bob 将第四个字母更改为“z”。
在第三个测试用例中:Alice 将第一个字母更改为“b”,然后 Bob 将第二个字母更改为“y”。