Yet Another String Game

题意翻译

有一个字符串 $s$，小A和小B在玩游戏，每人每次能选择字符串里的一个下标，把它改成一个新的字符（不能与原来的字符相等）。下标不能重复选择。 小A在游戏过程中，会尽量使新字符串的字典序最小，而小B会尽量使字符串字典序最大。 小A先开始游戏，且小A、小B足够聪明，每次一定能选择最优的方案。求问最终的字符串（即所有下标都被选过以后）是什么。 **本题每个测试点中有多组数据。** 第一行输入一个正整数 $t$，表示数据组数。 接下来每一行输入一个字符串 $s$。对于每一个测试点，也请输出一行字符串，表示答案。 ----- Translated By @[NSObject](https://www.luogu.com.cn/user/357545).

题目描述

Homer has two friends Alice and Bob. Both of them are string fans. One day, Alice and Bob decide to play a game on a string $ s = s_1 s_2 \dots s_n $ of length $ n $ consisting of lowercase English letters. They move in turns alternatively and Alice makes the first move. In a move, a player must choose an index $ i $ ( $ 1 \leq i \leq n $ ) that has not been chosen before, and change $ s_i $ to any other lowercase English letter $ c $ that $ c \neq s_i $ . When all indices have been chosen, the game ends. The goal of Alice is to make the final string lexicographically as small as possible, while the goal of Bob is to make the final string lexicographically as large as possible. Both of them are game experts, so they always play games optimally. Homer is not a game expert, so he wonders what the final string will be. A string $ a $ is lexicographically smaller than a string $ b $ if and only if one of the following holds: - $ a $ is a prefix of $ b $ , but $ a \ne b $ ; - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Description of the test cases follows. The only line of each test case contains a single string $ s $ ( $ 1 \leq |s| \leq 50 $ ) consisting of lowercase English letters.

输出格式

For each test case, print the final string in a single line.

输入输出样例

输入样例 #1

3
a
bbbb
az

输出样例 #1

b
azaz
by

说明

In the first test case: Alice makes the first move and must change the only letter to a different one, so she changes it to 'b'. In the second test case: Alice changes the first letter to 'a', then Bob changes the second letter to 'z', Alice changes the third letter to 'a' and then Bob changes the fourth letter to 'z'. In the third test case: Alice changes the first letter to 'b', and then Bob changes the second letter to 'y'.