Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Yet Another String Game

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputHomer 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$$$.

Input

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.

Output

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

Example

Input

3 a bbbb az

Output

b azaz by

Note

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'.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/23/2021 14:06:45 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|