In cryptography, the Caesar cipher, also known as the Caesar cipher, change cipher, Caesar code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter a fixed number of alphabetical up/down positions. This method is named after Julius Caesar, who used it in his private letters.

Encryption can also be expressed in arithmetic modulo by first converting the letters to the number, according to the scheme, A = 0, B = 1 ... Z = 25. Encrypt the message by a the change in n can be described mathematically as:

    E(x) = (x + n) mod 26

Input

The first line shows the number of test cases T of the problem (T <= 100).

Each test case is given on one line with:

• Starting with a natural number N indicates the displacement (0 <= N <= 100).
• Next is a string of uppercase characters less than 1000 characters long.

Output

• Begins with the character '#', followed by the sequence number of that test case, followed by a space and finally the string indicating the result of the Caesar encryption.

Example

Input:
2
3 THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
10 THE END

Output:
#1 WKH TXLFN EURZQ IRA MXPSV RYHU WKH ODCB GRJ
#2 DRO OXN