Playing Fair with Cryptography

Encryption turns plaintext into the matching ciphertext. One way to do it is the Playfair cipher, invented by Charles Wheatstone in the 1850s and named after Lyon Playfair, the Scottish scientist who promoted it hardest. Unlike many substitution ciphers, the Playfair cipher does not encrypt one letter at a time. It works on groups of two letters called digraphs.

Encryption uses a $5 \times 5$ grid built from a secret key that only the two parties know. Build the grid like this. Write the letters of the key into the grid, one letter per square, row by row starting at the top left, and skip any letter that already appeared. Then fill the remaining squares with the unused letters of the alphabet in order, with I and J sharing one square. For example, with the key "ECNA PROGRAMMING CONTEST" the grid is

Encrypt a digraph with these rules.

1. If both letters sit in the same row, replace each one with the letter immediately to its right, wrapping back to the start of the row at the end. With the grid above, the plaintext digraph DS encrypts to FB, and AP encrypts to PE.
2. If both letters sit in the same column, replace each one with the letter immediately below it, wrapping back to the top of the column at the bottom. PF encrypts to IU (or JU), and WO encrypts to CS.
3. Otherwise slide the first letter along its row until it lands in the column of the second letter, and slide the second letter the same way. The two letters you land on are the ciphertext for the digraph. Reading the original digraph as two corners of a rectangle in the grid, you replace them with the letters at the other two corners. TU encrypts to FH, UT encrypts to HF, and ZC encrypts to WP.

What happens when a digraph holds the same letter twice? The original Playfair cipher inserts the letter 'X' between the two letters and keeps encrypting. It also appends one extra 'X' when the plaintext has an odd number of letters. So the plaintext "OOPS" first becomes the digraphs "OX", "OP" and "SX", which the grid above encrypts as "GWICBW". The plaintext "POOS" needs no added letter, because the two 'O's never land in the same digraph.

This problem changes the Playfair cipher in one way. Instead of always inserting 'X', insert 'A' the first time an insertion is needed, then 'B' the next time, and so on. Never insert 'J': go straight from 'I' to 'K'. Once you use 'Z' you start over at 'A'. If the letter you are about to insert would produce a digraph with two identical letters, skip it and use the next one. Under this rule "OOPS" becomes the digraph stream "OA", "OP", "SB", and the plaintext "AABCC" becomes "AB", "AB", "CD", "CE".

Given a key and a plaintext, produce the corresponding ciphertext.

The first line holds an integer $n$, the number of problem instances. Each instance takes two lines: the key on the first line, and the plaintext to encrypt on the second. Both lines may hold upper-case and lower-case letters, spaces, and non-alphabetic characters. Ignore the spaces and the non-alphabetic characters. The letters 'j' and 'J' never appear in a key or a plaintext.

For each problem instance print one line holding Case k: followed by the ciphertext, where $k$ is the instance number starting at 1. Write the ciphertext in upper-case letters with no spaces, and always use 'I' in place of 'J'.