The Myszkowski cipher encrypts text messages by rearranging the original message according to a certain keyword. For example, suppose we want to encrypt the plaintext VERY SENSITIVE INFORMATION HERE using the keyword TOMATO. The cipher proceeds as follows:
The plaintext is split into rows, with all spaces ignored. Each row should be the same length as the keyword, except possibly the last row.
V E R Y S E N S I T I V E I N F O R M A T I O N H E R E
The columns are each assigned a rank, according to the relative alphabetical order of the letters in the keyword. With the keyword TOMATO, we have $\texttt{A} < \texttt{M} < \texttt{O} < \texttt{T}$, so the column ranks are:
4 3 2 1 4 3 V E R Y S E N S I T I V E I N F O R M A T I O N H E R E
To produce the ciphertext, the letters of the plaintext are transcribed in the order of the column ranks. If a column’s rank appears exactly once, the letters are transcribed downward. If a column’s rank appears more than once, the letters are transcribed from left to right, then top to bottom, across all columns with that rank.
A space is inserted after every 5 characters of the ciphertext. However, there should never be a trailing space at the end of the ciphertext.
In this example, we start from the column with rank 1 and transcribe downward, since rank 1 appears only once:
YTFIE
We then move to the column with rank 2 and again transcribe downward, since rank 2 appears only once:
YTFIE RINTR
We then move to rank 3. Since rank 3 appears more than once, we transcribe across all columns with rank 3:
YTFIE RINTR EESVI RANE
Finally, we move to the leftmost column with rank 4. Since rank 4 appears more than once, we transcribe across all columns with rank 4:
YTFIE RINTR EESVI RANEV SNIEO MOH
Input begins with a number $n$ on a single line, denoting the number of messages to encrypt, with $1 \leq n \leq 100$.
$n$ lines follow. Each line begins with a keyword (which cannot contain any spaces), followed by a space, followed by a message to encrypt. The message may contain any number of space-separated words. The number of characters in the message (excluding spaces) is at least the number of characters in the keyword. Both the keyword and the message contain only upper-case letters.
For each keyword and message, output the resulting ciphertext.
Sample Input 1 | Sample Output 1 |
---|---|
1 TOMATO VERY SENSITIVE INFORMATION HERE |
YTFIE RINTR EESVI RANEV SNIEO MOH |