CCSC Mid-South Programming Contest

Start

2018-04-06 10:00 AKDT

CCSC Mid-South Programming Contest

End

2018-04-06 14:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -901 days 4:25:49

Time elapsed

4:00:00

Time remaining

0:00:00

Problem D
Myszkowski 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