Problem G
It's a Secret

In junior high, you were fascinated by secret codes. When you discovered the Playfair cipher, you shared the knowledge with a friend, and the two of you started using the cipher in order to pass notes in class without fearing that they would be read if intercepted. Because you enjoyed this so much at the time, you have continued to encode all of your correspondence in cipher. However, since you now attend different universities, your messages have become longer and more frequent. You would like to save time by writing a program to encode your messages.

The Playfair Cipher

The Playfair cipher uses a key word or phrase to generate a 5 by 5 table. To do this, fill in the spaces in the table with the letters of the keyword in row major order, ignoring subsequent occurrences of the same letter and any spaces and replacing any instances of the letter “J” with “I”. Fill any remaining spaces with the rest of the letters of the alphabet in order, excluding the letter “J”.

Example: The keyword “Playfair” would generate the key table:

To encrypt a message, break it into digraphs (groups of 2 letters) such that, for example, “Hello World” becomes “HE LL OW OR LD”. Make sure to apply the following rules:

• Ignore spaces, and convert all letters to upper case.

• Convert all instances of the letter “J” in your message to “I”.

• If both letters in the digraph are the same, add an "X" after the first letter, rearranging the subsequent digraphs if necessary (e.g. If the message is “Whoop”, it breaks into the digraphs, “WH OX OP”).

• If a letter is left without a partner, add an “X” at the end.

Then, encode each digraph in the message by applying the following rules:

• If the letters are not on the same row or column, look along the row of each letter in the digraph until you reach the column that has the other letter in the digraph. The letter at this intersection replaces the original letter.

• If the letters appear on the same row of the table, replace each with the letter to its immediate right. If a letter is at the end of its row, replace it with the letter at the beginning.

• If the letters appear on the same column of the table, replace each with the letter directly beneath it. If a letter is at the bottom of its row, replace it with the letter at the top.

• If the digraph is “XX”, always replace it with “YY”.

Example:

(1)                 (2)                 (3)
Z * * O *           * * O * *           * * * * *
* * * * *           * * B * *           * O Y R Z
* * * * *           * * * * *           * * * * *
R * * X *           * * R * *           * * * * *
* * * * *           * * Y * *           * * * * *
Hence, OR -> ZX     Hence, OR -> BY     Hence, OR -> YZ

Input

Input will consist of up to $50$ test cases. Each will begin with the number of lines to be encoded, $1 \le n \le 50$. This will be followed by a single line that contains the key phrase for the cipher. After this comes $n$ lines of text to encrypt. All input besides $n$ will consist only of alphabetic characters (a–z, A–Z) or spaces with length in the range $[1,50]$. Input ends when $n = 0$.

Output

For each test case, output the encoded lines of text. All letters should be in upper case. Output a blank line between adjacent cases.

4
ThisIsATest
AQuickBrownFox
JumpedOverTheLazyDogs
Playfair ciphers are fun
Hooray for cryptology
2
Just another example
Meet me at eight o clock
Signed Agent Double O Eight
0

IUQABLDPPVUNQV
AQKRBFVTDOHICGFASMVOIY
QKSZNFSQLCWBDOATODNZLZ
TPPUSZEUQDYSOHQGVOZY

LOLELOIANTFEUEGXNDCB
TUCEOGTKROUGMOXBRHNTFEIL