IUST Problem D

Time Limit: 3 Seconds    Memory Limit: 32768 KB

A hacker, who has stolen a lot of important information, wants to encrypt them in his computer so that only he can access them. He has devised an algorithm he thinks is unbreakable because no one would expect something like it.

To “Decrypt” a text in his system, one should start from the first character directly after the one and only “*” character of the Encrypted string, which is also the first character of the original text. Every time, we find the ASCII code of the current character, (for e.g. 60), start from the beginning, and go that number of times forward until we get to a new character (So we would be on the 60th character of the encrypted string in the previous example). If during this process we get to the end of the string, we resume counting from the beginning of the text (Which means in the previous example, if the length of the string is 13 and the character we read had the ASCII code of 60, in the end we would be looking at the 9th character of the string). After each process, the character we reach is the next character of the original string, and also we should start the next process using this one’s ASCII code. If during this, we reach a character we had read before or we went back to the “*” character (For example, if we are going to read the 9th character for the second time), we should instead find the first character we have not read yet directly after the current one and resume the process using it.

 

One important thing to note is that if we remove the “*” from the encrypted string, and see it as a number in base 256 (Which means that each character in the string counts as a digit, with the ASCII code being the value), it is the largest possible such number that, if decrypted, results in the original string.

 

Now, write a program that, given the original text, gives the encrypted one as output.

 

 

Input

The program should get N (N < 32768), which is the number of input strings, and then, get that number  of strings consisting solely of letters (a, b, c, …, z, A, B, C, … Z).

Output

 The program should print the encrypted text for each of these inputs in separated lines.

 

Sample Input

3
salam
pashmak
kolahghermezi

Sample Output

salam*
s*pamhak
zirmh*kgeoaehl

Submit

Source: 12th Iran Nationwide Internet Contest II