You have been tasked to create a program to decrypt a simple encrypted message. The steps to encrypt messages in this format are to:

1. Reverse the message content
2. Move every third (3rd, 6th, 9th...) character to the end of the message (sequentially)
3. Change each letter to the next letter of the alphabet (a → b, b → c ... z → a)

For example, by following the steps above the message "abbcdd" is encrypted as follows:

1. ddcbba
2. ddbbca
3. eeccdb

Your program must decrypt the given encrypted messages.

Input

The first line contains a single positive integer N. The next N lines each contain a single message composed of lowercase alphabetic characters (a-z).

Output

For each of the N lines, output the decrypted message as a string of lowercase alphabetic characters.

Example

Input:
2
eeccdb
uijsjuhvztpjbmubhodhuppouvsp

Output
abbcdd
congratulationsyougotitright