题目描述

Homer 有两个朋友，Alice 和 Bob。他们都是字符串爱好者。

一天，Alice 和 Bob 决定在一个长度为 $n$ 的字符串 $s = s_1 s_2 \dots s_n$ 上玩一个游戏，字符串仅包含小写英文字母。他们轮流操作，Alice 先手。

每次操作时，玩家必须选择一个之前未被选择过的下标 $i$（$1 \leq i \leq n$），并将 $s_i$ 改为任意一个不同于 $s_i$ 的小写英文字母 $c$（即 $c \neq s_i$）。

当所有下标都被选择过后，游戏结束。

Alice 的目标是让最终的字符串字典序尽可能小，而 Bob 的目标是让最终的字符串字典序尽可能大。他们都是游戏高手，因此总是以最优策略进行游戏。Homer 不是游戏高手，所以他想知道最终的字符串会是什么。

如果字符串 $a$ 满足以下任一条件，则称 $a$ 的字典序小于字符串 $b$：

• $a$ 是 $b$ 的前缀，且 $a \ne b$；
• 在 $a$ 和 $b$ 第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试数据的组数。接下来每组测试数据包含一行，仅包含一个由小写英文字母组成的字符串 $s$（$1 \leq |s| \leq 50$）。

输出格式

对于每组测试数据，输出最终的字符串，每行一个。

说明/提示

第一组样例：Alice 先手，必须将唯一的字母改为不同的字母，因此她将其改为 'b'。

第二组样例：Alice 将第一个字母改为 'a'，Bob 将第二个字母改为 'z'，Alice 将第三个字母改为 'a'，Bob 将第四个字母改为 'z'。

第三组样例：Alice 将第一个字母改为 'b'，Bob 将第二个字母改为 'y'。

由 ChatGPT 4.1 翻译

样例

3
a
bbbb
az

b
azaz
by