DCRYPT - Decrypt the message !

no tags 

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

hide comments
numerix: 2013-11-19 22:42:39

@Saimadhav Heblikar: It's advisable to develop well designed code. It's no problem to get AC with Python e.g.

Saimadhav Heblikar: 2013-11-17 04:55:44

TLE in python,AC in c for the same logic.advisable not to use interpreted languages.

Mauro Persano: 2013-11-02 18:32:29

I/O-bound problem, time limit should be looser to allow interpreted languages.

Alien: 2013-10-30 11:28:42

@pandian what is meant by "modulo is taken"?


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