Hide

# Problem DMyszkowski Cipher

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

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.

## Output

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