Naruto has used a Jutsu to encrypt a top secret message consisting of any possible character of length <= 1000, he wants to send to Sakura Chan. You are a ninja of Hidden Mist Village, and your task is to decrypt it by using following rules:-

You have to output a string such that:-

• If the letter is lowercase convert it into uppercase and vice versa.
• if there is a special character (any character other than numbers, letters, space) convert it into dot(.).
• any number appearing as a substring is to be converted into corresponding lowercase letter (a for 1, b for 2 ... z for 0) and if the number is greater than 26 then the number is modulo 26.

Input

First line of input tells number of test cases (t <= 100). Each of next t lines contain a string s (|s| <= 1000).

Output

For each test case output Naruto's message.

Example

Input:
1
Ha74E 235 144i3e 82A51*:)

Output:
hAve a nIcE day...