DCRYPT - Decrypt the message !

Krishna loves Radha and wants to propose her in a different way. He wants to tell her the message, but he wanted the message to be a surprise. So, he plans to encrypt the message and send the encrypted message to Radha and he also gives the key to decrypt. He thinks that this might be a surprise to Radha. Help Radha to decrypt the message.

Rules of encryption :

0 ≤ key ≤ 51

The original message only consists of a-z, A-Z, and space.

Spaces are encrypted as '.'

If key lies between 0 and 25, then the character is added with the key and modulo is taken and the case is maintained. For eg, if key is 3, then a is decrypted to d and e is decrypted to h.

If key lies between 26 and 51, then the character is added with the key and modulo is taken and the case is inverted. For eg, if key is 29, then a is decrypted to D and E is decrypted to h.

Input

First line consists of t, the number of test cases. (1 ≤ t ≤ 20)

For each test case, first line consists of key. 0 ≤ key ≤ 51

Second line consists of the encrypted message S. |S| ≤ 100000

Output

For each test case, display the decrypted message in a separate line.

Example

Input:
1
2
dsz.dsf
Output: fub fuh

Added by:Pandian
Date:2013-10-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem

hide comments
2017-11-30 17:21:01
Easy one !!!
2017-09-20 10:30:18
Try GCPC11F if you enjoyed this.
2016-02-08 21:06:17
2 much if-else !!!
2015-07-31 18:46:43
careful when (int)char >128..
2015-06-29 21:29:57 Sandip Jana
MY 100TH :D

Last edit: 2015-06-29 21:30:28
2015-06-28 11:09:18 Manishi Goel
what should be the output if the encrypted message is .abc.
should it be( space)cde(space) or cde for any key...here key=2;


Last edit: 2015-07-02 07:07:39
2015-05-31 08:05:23 ---@@@----
Easy one.. !!!
2015-03-29 06:29:10 darol
use StringBuilder in java
2015-01-05 18:29:56 :.Mohib.:
AC.....Just love encryption.... :)
2013-12-03 07:45:11 Alexandre Henrique Afonso Campos
@khan@
Modulo is taken means taking the key modulo 26. Eg: if key==28, you will change the case and consider new key==2.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.