Cipher X26991

The Caesar cipher is one of the oldest and most widely known encryption techniques. Given a text message and a fixed integer S (the right shift), each letter in the message is replaced by the letter that comes S positions after it in the alphabet. Note that the alphabet is treated as cyclic (so that ‘A’ comes after ‘Z’) and that spaces in the message are not encrypted.

Your task is to write a program that encrypts a message using a given right shift.

Input

The input starts with the number of test cases T ≤ 1000. For each test case, the input contains the right shift S with 0≤ S < 26, followed by the message to be encrypted on a separate line. All letters of the message are uppercase, and the message may contain spaces, but the first character of the message is always a letter.

Output

For each test case, output the encrypted message on a single line.