Shift Cypher

Introduction

If you have ever been a fourth grader who needed to share a secret message, you probably used a shift cypher to encrypt it. A shift cypher simply shifts the alphabet forwards or backwards a certain number of letters. This number is only known to the sender and receiver, ensuring secrecy if the message was intercepted. For example, a shift of one forward would encrypt ZEBRA to AFCSB. A shift of two would produce BGDTC, and so on. Notice how Z wraps back around to A. Also, spaces between words are not modified. This cypher can easily be cracked used frequency analysis, which is not as complicated as it sounds. As you may know, the letter ‘e’ is the most common letter used in English. Take any piece of text and count the occurrences of each letter. E will have a clear lead. Now do that with a piece of text encrypted with a shift cypher. There will be a letter that has a clear lead, and we know that it is e in the decrypted message. From this, we can find the shift and the cypher has been cracked. My challenge to you is to write a program that can do this by itself.

Input:
The first line of input is an integer T, denoting the number of test cases. The next T lines each contain a string of text which should be decrypted using the frequency analysis method described above. Each line has a different shift applied to it, but each character on a single line has the same shift. The strings of text consist of only lowercase letters and spaces.

Output:
For each test case, print a line containing the decrypted message.

Sample Input

3
bpqa xpmvwumvwv epmzm wvm tmbbmz pia i vwbqkmijtg pqopmz nzmycmvkg
xjhkvmzy oj vit joczm gzoozm dn ijo nzzi jigt di zibgdnc do zsdnon di
qvjgt ncpiwcigu nkmg hqt gzcorng urcpkuj


Sample Output

this phenomenon where one letter has a noticeably higher frequency
compared to any other letter is not seen only in english it exists in
other languages like for example spanish