Cipher

The Playfair cipher or Playfair square is a manual symmetric encryption technique and was the first literal digraph
substitution cipher. The technique encrypts pairs of letters (digraphs), instead of single letters as in the simple
substitution cipher and rather more complex Vigenère cipher systems then in use. The Playfair is thus significantly harder
to break since the frequency analysis used for simple substitution ciphers does not work with it. Frequency analysis can still
be undertaken, but on the 600 possible digraphs rather than the 26 possible monographs. The frequency analysis of digraphs
is possible, but considerably more difficult and it generally requires a much larger ciphertext in order to be useful.

Despite its invention by Wheatstone, it became known as the Playfair cipher after Lord Playfair, who heavily promoted its
use. The first recorded description of the Playfair cipher was in a document signed by Wheatstone on 26 March 1854.It was
used for tactical purposes by British forces in the Second Boer War and in World War I and for the same purpose by the
Australians and Germans during World War II. This was because Playfair is reasonably fast to use and requires no special
equipment. A typical scenario for Playfair use would be to protect important but non-critical secrets during actual combat.
By the time the enemy cryptanalysts could break the message, the information was useless to them.

However Playfair is no longer used by military forces because of the advent of digital encryption devices. Playfair is now
regarded as insecure for any purpose because modern hand-held computers could easily break the cipher within seconds.

The Playfair cipher uses a 5 by 5 table containing a keyword or phrase. Memorization of the keyword and some simple
rules was all that was required to create the 5 by 5 table and use the cipher.
To generate the key table, one would first
fill in the spaces in the table with the letters of the keyword (dropping any duplicate letters), then fill the remaining
spaces with the rest of the letters of the alphabet in order (combine 'I' and 'J' to reduce the alphabet to fit).

To encrypt a message, one would change the lowercase to uppercase, break the message into digraphs (groups of 2 letters
and throw away spaces) such that, for example, "Hello World" becomes "HE LL OW OR LD", and map them out on the key table.
The two letters of the digraph look like the corners of a rectangle in the key
table. Note the relative position of the corners of this rectangle. Then apply the following rules, in order, to each pair
of letters in the plaintext:
If both letters are the same (or only one letter is left), add an 'X' after the first letter. Encrypt the new pair and continue.

If the letters appear on the same row of your table, replace them with the letters to their immediate right respectively
(wrapping around to the left side of the row if a letter in the original pair was on the right side of the row).

If the letters appear on the same column of your table, replace them with the letters immediately below respectively
(wrapping around to the top side of the column if a letter in the original pair was on the bottom side of the column).

If the letters are not on the same row or column, replace them with the letters on the same row respectively but at the
other pair of corners of the rectangle defined by the original pair.
The order is important-the first encrypted letter of the pair is the one that lies on the same row as the first plaintext letter.

The input consists of multiple test cases. The first line of input contains an integer T, which is the number of test cases.
Each test case containing two lines: the key and the message.
The length of the key and the message will
not exceed 500.
You may assume that the message does not contain substring such as "XX", "IJ" , "JI", and does not end with "X".

For each test case, print one line containing the encrypted message.

3
Charles 
Meet me at the Hammersmith Bridge tonight 
Death 
Laboulaye Lady 
to go to jail together 
to stand up for freedom together 

GDVBYTBCQYPRSCRKYKDCDIMPASHMEMDOUGKIRP 
MEIKQOTXCQTEZY 
OGNITUMPQDIEKHHWDPADOGOHGLHB 

Hint1.
Using "Death" as the key, the table becomes:
D E A T H
B C F G I / J
K L M N O
P Q R S U
V W X Y Z

NOTE that 'J' is in same place with 'I'!

Encrypting the message "Laboulaye Lady":
LA BO UL AY EL AD YX

The pair LA forms a rectangle, replace it with ME.
The pair BO forms a rectangle, replace it with IK.
The pair UL forms a rectangle, replace it with QO.
The pair AY forms a rectangle, replace it with TX.
The pair EL in a column, replace it with CQ.
The pair AD in a row, replace it with TE.
The pair YX in a row, replace it with ZY.

ME IK QO TX CQ TE ZY
Thus the message becomes "MEIKQOTXCQTEZY".
2.
Assume one wants to encrypt the digraph OR. There are three general cases:
1) 2) 3)
* * * * * * * O * * Z * * O *
* O Y R Z * * B * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * R * * R * * X *
* * * * * * * Y * * * * * * *
Hence, OR -> YZ Hence, OR -> BY Hence, OR -> ZX

The 4th Baidu Cup Central China Invitational Programming Contest